Two sides of the coin problem

Gil Cohen, Anat Ganor, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

In the coin problem, one is given n independent flips of a coin that has bias β > 0 towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply the majority function on the n samples. This simple strategy works as long as β > Ω(1/√n). However, computing majority is an impossible task for several natural computational models, such as bounded width read once branching programs and AC0 circuits. Brody and Verbin [8] proved that a length n, width w read once branching program cannot solve the coin problem for β < O(1/(logn)w). This result was tightened by Steinberger [20] to O(1/(log n)w-2). The coin problem in the model of AC0 circuits was first studied by Shaltiel and Viola [19], and later by Aaronson [1] who proved that a depth d size s Boolean circuit cannot solve the coin problem for β < O(1/(logs)d+2). This work has two contributions: We strengthen Steinberger result and show that any Santha-Vazirani source with bias β < O(1/(log n)w-2) fools length n, width w read once branching programs. In other words, the strong independence assumption in the coin problem is completely redundant in the model of read once branching programs, assuming the bias remains small. That is, the exact same result holds for a much more general class of sources. We tighten Aaronson's result and show that a depth d, size s Boolean circuit cannot solve the coin problem for β < O(1/(logs)d-1). Moreover, our proof technique is different and we believe that it is simpler and more natural.

Original languageEnglish (US)
Title of host publicationLeibniz International Proceedings in Informatics, LIPIcs
EditorsKlaus Jansen, Cristopher Moore, Nikhil R. Devanur, Jose D. P. Rolim
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages618-629
Number of pages12
ISBN (Electronic)9783939897743
DOIs
StatePublished - Sep 1 2014
Event17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 - Barcelona, Spain
Duration: Sep 4 2014Sep 6 2014

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume28
ISSN (Print)1868-8969

Other

Other17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014
CountrySpain
CityBarcelona
Period9/4/149/6/14

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Two sides of the coin problem'. Together they form a unique fingerprint.

  • Cite this

    Cohen, G., Ganor, A., & Raz, R. (2014). Two sides of the coin problem. In K. Jansen, C. Moore, N. R. Devanur, & J. D. P. Rolim (Eds.), Leibniz International Proceedings in Informatics, LIPIcs (pp. 618-629). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 28). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.618