Computer Science/Discrete Mathematics Seminar I
Influences, Traces, Tribes, and Perhaps Also Thresholds
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.