Theory of Computing
-------------------
Title : Influential Coalitions for Boolean Functions I: Constructions
Authors : Jean Bourgain, Jeff Kahn, and Gil Kalai
Volume : 20
Number : 4
Pages : 1-13
URL : https://theoryofcomputing.org/articles/v020a004
Abstract
--------
For f:{0,1}^n --> {0,1} and S\subset {1,2,\dots,n},
let J^+_S(f) be the probability that, for x uniform from
{0,1}^n, there is some y\in {0,1}^n with f(y)=1 and
x\equiv y outside S. We are interested in estimating, for given
\mu(f) (:= \mathbb E(f)) and m, the least possible value of
\max{J^+_S(f): |S|=m}.
A theorem of Kahn, Kalai, and Linial (KKL) gave some understanding of
this issue and led to several stronger conjectures. Here we disprove a
pair of conjectures from the late 80s, as follows.
(1) The KKL Theorem implies that there is a fixed \alpha> 0 so
that if \mu(f)\approx 1/2, and c> 0, then there is a set S of
size at most \alpha cn with J^+_S(f) \ge 1-n^{-c}. We show that
for every \delta > 0 there is an f with \mu(f)\approx 1/2 and
J^+_S(f)\le 1-n^{-C} for every S of size (1/2-\delta)n,
where C=C_\delta. This disproves a conjecture of Benny Chor from
1989.
(2) We also show that for fixed \gd> 0 there are c,\ga > 0 and
Boolean functions f such that \mu(f) > \exp[-n^{1-c}] and
J^+_S(f) \le \exp[-n^\ga] for each S of size (1/2-\gd)n.
This disproves a conjecture of the third author from the late 80s.