| 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 |
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.