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.