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.