A Resolution of Friedgut's Conjecture on Influential Coalitions

Abstract

We prove that, for every constant $\epsilon >0$ and every function $f:{\Sigma }^n\to \{0,1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in \{0,1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output equal to $b$ with probability at least $1-\epsilon$. The bound is independent of the alphabet size and also holds for monotone Boolean functions on $[0,1{]}^n$, resolving a conjecture of Friedgut (Combinatorics, Probability and Computing, 2004). Unlike the Boolean cube setting, where Kahn, Kalai, and Linial (FOCS, 1988) give a coalition bound of $O(n/\log n)$, no sublinear bound independent of the alphabet size was previously known. In collective coin flipping, our result gives the first sublinear bound on the number of bad players needed to force a fixed output with probability at least $1-\epsilon$ in any one-round protocol with independent uniform messages, regardless of the message length. A key ingredient in our proof is an encoding that lets us relate the influence of a function on a product space to the $p$-biased influence of the encoded function. We then rely on a structure theorem of Hatami (Annals of Mathematics, 2012) for functions with small $p$-biased influence to bias the encoded function.