ECCC-Report TR19-029https://eccc.weizmann.ac.il/report/2019/029Comments and Revisions published for TR19-029en-usSun, 03 Mar 2019 07:20:51 +0200
Paper TR19-029
| Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions |
Yuval Filmus,
Lianna Hambardzumyan,
Hamed Hatami,
Pooya Hatami,
David Zuckerman
https://eccc.weizmann.ac.il/report/2019/029The seminal result of Kahn, Kalai and Linial shows that a coalition of $O(\frac{n}{\log n})$ players can bias the outcome of *any* Boolean function $\{0,1\}^n \to \{0,1\}$ with respect to the uniform measure. We extend their result to arbitrary product measures on $\{0,1\}^n$, by combining their argument with a completely different argument that handles very biased coordinates.
We view this result as a step towards proving a conjecture of Friedgut, which states that Boolean functions on the continuous cube $[0,1]^n$ (or, equivalently, on $\{1,\dots,n\}^n$) can be biased using coalitions of $o(n)$ players. This is the first step taken in this direction since Friedgut proposed the conjecture in 2004.
Russell, Saks and Zuckerman extended the result of Kahn, Kalai and Linial to multi-round protocols, showing that when the number of rounds is $o(\log^* n)$, a coalition of $o(n)$ players can bias the outcome with respect to the uniform measure. We extend this result as well to arbitrary product measures on $\{0,1\}^n$.
The argument of Russell et al.\ relies on the fact that a coalition of $o(n)$ players can boost the expectation of any Boolean function from $\epsilon$ to $1-\epsilon$ with respect to the uniform measure. This fails for general product distributions, as the example of the AND function with respect to $\mu_{1-1/n}$ shows. Instead, we use a novel boosting argument alongside a generalization of our first result to arbitrary finite ranges.Sun, 03 Mar 2019 07:20:51 +0200https://eccc.weizmann.ac.il/report/2019/029