Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

Authors Yuval Filmus , Lianna Hambardzumyan, Hamed Hatami , Pooya Hatami , David Zuckerman



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.58.pdf
  • Filesize: 478 kB
  • 13 pages

Document Identifiers

Author Details

Yuval Filmus
  • Computer Science Department, Technion, Haifa, Israel
Lianna Hambardzumyan
  • School of Computer Science, McGill University, Montreal, QC, Canada
Hamed Hatami
  • School of Computer Science, McGill University, Montreal, QC, Canada
Pooya Hatami
  • Department of Computer Science, UT Austin, Austin, TX, USA
David Zuckerman
  • Department of Computer Science, UT Austin, Austin, TX, USA

Acknowledgements

Part of the work on this paper was done while the first three authors were at the Simons Institute for the Theory of Computing at Berkeley, CA, USA.

Cite AsGet BibTex

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, and David Zuckerman. Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.58

Abstract

The seminal result of Kahn, Kalai and Linial shows that a coalition of O(n/(log n)) players can bias the outcome of any Boolean function {0,1}^n -> {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 input bits. 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,...,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.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Boolean function analysis
  • coin flipping

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Miklós Ajtai and Nathan Linial. The influence of large coalitions. Combinatorica, 13(2):129-145, 1993. Google Scholar
  2. Michael Ben-Or and Nathan Linial. Collective coin flipping. Advances in Computing Research, 5:91-115, 1989. Google Scholar
  3. Michael Ben-Or, Nathan Linial, and Michael Saks. Collective coin flipping and other models of imperfect randomness. IBM Thomas J. Watson Research Division, 1989. Google Scholar
  4. Jean Bourgain, Jeff Kahn, Gil Kalai, Yitzhak Katznelson, and Nathan Linial. The influence of variables in product spaces. Israel Journal of Mathematics, 77(1-2):55-64, 1992. Google Scholar
  5. Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. Annals of Mathematics, to appear, 2016. Preliminary version in STOC 2016. Google Scholar
  6. Benny Chor and Cynthia Dwork. Randomization in Byzantine Agreement. Advances in Computing Research, 5:443-497, 1989. Google Scholar
  7. Yevgeniy Dodis. Fault-tolerant leader election and collective coin-flipping in the full information model. Survey, 2006. Google Scholar
  8. Uriel Feige. Noncryptographic Selection Protocols. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, page 142. IEEE Computer Society, 1999. Google Scholar
  9. Ehud Friedgut. Influences in Product Spaces: KKL and BKKKL Revisited. Combinatorics, Probability and Computing, 13(1):17-29, 2004. Google Scholar
  10. Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on Boolean functions. In Proceedings of the 29th annual FOCS, pages 68-80, 1988. Google Scholar
  11. Raghu Meka. Explicit resilient functions matching Ajtai-Linial. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1132-1148. SIAM, 2017. Google Scholar
  12. Alexander Russell, Michael Saks, and David Zuckerman. Lower bounds for leader election and collective coin-flipping in the perfect information model. SIAM Journal on Computing, 31(6):1645-1662, 2002. Google Scholar
  13. Alexander Russell and David Zuckerman. Perfect information leader election in log* n+ O (1) rounds. Journal of Computer and System Sciences, 63(4):612-626, 2001. Google Scholar
  14. Terence Tao. Soft analysis, hard analysis, and the finite convergence principle. URL: https://terrytao.wordpress.com/2007/05/23/soft-analysis-hard-analysis-and-the-finite-convergence-principle/, 2007. Accessed 10 Feb 2019.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail