Sublinear size coalitions can control outputs in complex systems
A Resolution of Friedgut's Conjecture on Influential Coalitions
Computational ComplexityDiscrete Mathematics
Summary
Figuring out which small groups of inputs can strongly influence the outcome of a complex function has been a tricky problem, especially when those inputs come from large sets. The authors proved that for any function taking many inputs, there's a relatively small group of them that can be set to force the output to a certain value with very high chance. This resolves a long-standing question and works even when inputs come from large or continuous sets. Their approach used clever encoding techniques and previously known structural insights to make this result possible.
What this means in practice
- •For cryptography engineers: Design more resilient protocols by understanding minimal coalition sizes needed to bias outputs in collective coin flipping schemes.
- •For distributed systems developers: Evaluate the vulnerability of distributed decision processes to small groups of coordinated inputs influencing the outcome.
A theory result. No direct application yet.
Authors
Eshan Chattopadhyay, Mohit Gurumukhani
Abstract
We prove that, for every constant $\varepsilon>0$ and every function $f:Σ^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-\varepsilon$. 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-\varepsilon$ 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.