Title | ||
---|---|---|
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. |
Abstract | ||
---|---|---|
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 {0,1}$ with respect to the uniform measure. 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. 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. |
Year | Venue | DocType |
---|---|---|
2019 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
26 | 0 | 0.34 |
References | Authors | |
2 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yuval Filmus | 1 | 275 | 27.33 |
Lianna Hambardzumyan | 2 | 0 | 0.34 |
Hamed Hatami | 3 | 216 | 23.09 |
Pooya Hatami | 4 | 94 | 14.40 |
David Zucherman | 5 | 2588 | 266.65 |