KKL theorem for the influence of a set of variables

Abstract

Consider a Boolean function f on the n-dimensional hypercube, and a set of variables (indexed by) $S\subset \{1,2,\dots ,n\}.$ The coalition influence of the variables S on a function f is the probability that after a random assignment of variables not in S, the value of f is undetermined. In this paper, we study a complementary notion, which we call the joint influence: the probability that, after a random assignment of variables not in S, the value of f is dependent on all variables in S. We show that for an arbitrary fixed d, every Boolean function f on n variables admits a d-set of joint influence at least $\frac{1}{10}{W}^{\ge d}(f)(\frac{\log n}{n}{)}^d$, where $W^{\ge d}(f)$ is the Fourier weight of f at degrees at least d. This result is a direct generalisation of the Kahn-Kalai-Linial theorem. Further, we give an example demonstrating essential sharpness of the above bound. In our study of the joint influence we consider another notion of multi-bit influence recently introduced by Tal.

To appear in SIAM journal on Discrete Mathematics