Computer Science/Discrete Mathematics Seminar I | |

Topic: | Influences, Traces, Tribes, and Perhaps Also Thresholds |

Speaker: | Gil Kalai |

Affiliation: | Hebrew University; Yale University |

Date: | Monday, February 4 |

Time/Room: | 11:15am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/1213/csdm/0204-GilKalai |

I will describe some recent results and problems regarding influence of sets of variables on Boolean functions: In 1989 Benny Chor conjectured that a balanced Boolean function with n variables has a subset S of size 0.4n with influence (1-c^n) where c<1. The existence of a set S with influence (1-1/n^c) for some c>0 follows from a theorem by Kahn, Kalai and Linial (KKL).I will present a recent counterexample by Kahn and me showing that up to the identity of c, the KKL bound cannot be improved. I will discuss also relations with traces and with Suaer-Shelah theorem, some related new constructions with Jeff Kahn, and earlier constructions by Bollobas and Radcliffe and by Shelah and me. I will also discuss some conjectures with Kahn on the large threshold interval of a monotone Boolean function.