Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-023 | 9th March 2014 11:45

Two Sides of the Coin Problem

RSS-Feed




Revision #1
Authors: Gil Cohen, Anat Ganor, Ran Raz
Accepted on: 9th March 2014 11:45
Downloads: 1874
Keywords: 


Abstract:

In the Coin Problem, one is given n independent flips of a coin that has bias $\beta > 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 $\beta > \Omega(1/\sqrt{n})$. However, computing majority is an impossible task for several natural computational models, such as bounded width read once branching programs and $AC^0$ circuits.

Brody and Verbin [FOCS 2010] proved that a length n, width w read once branching program cannot solve the coin problem for $\beta < O(1/(\log{n})^{3w})$. This result was tightened by Steinberger [CCC 2013] to $O(1/({\log{n}})^{w-2})$. The coin problem in the model of $AC^0$ circuits was first studied by Shaltiel and Viola [STOC 2008], and later by Aaronson [STOC 2010] who proved that a depth d size s Boolean circuit cannot solve the coin problem for $\beta < O(1/(\log{s})^{d+2})$.

This work has two contributions:

1. We strengthen Steinberger result and show that any Santha-Vazirani source with bias $\beta < 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. That is, the exact same result holds for a much more general class of sources.

2. We tighten Aaronson result and show that a depth d, size s Boolean circuit cannot solve the coin problem for $\beta < O(1/(\log{s})^{d-1})$. Moreover, our proof technique is different and we believe that it is simpler and more natural.



Changes to previous version:

Main change is an additional reference to a paper of Shaltiel and Viola [STOC 2008].


Paper:

TR14-023 | 19th February 2014 21:54

Two Sides of the Coin Problem





TR14-023
Authors: Gil Cohen, Anat Ganor, Ran Raz
Publication: 19th February 2014 22:02
Downloads: 2978
Keywords: 


Abstract:

In the Coin Problem, one is given n independent flips of a coin that has bias $\beta > 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 $\beta > \Omega(1/\sqrt{n})$. However, computing majority is an impossible task for several natural computational models, such as bounded width read once branching programs and $AC^0$ circuits.

Brody and Verbin [FOCS 2010] proved that a length n, width w read once branching program cannot solve the coin problem for $\beta < O(1/(\log{n})^{3w})$. This result was tightened by Steinberger [CCC 2013] to $O(1/({\log{n}})^{w-2})$. As for the model of $AC^0$ circuits, Aaronson [STOC 2010] proved that a depth d size s Boolean circuit cannot solve the coin problem for $\beta < O(1/(\log{s})^{d+2})$.

This work has two contributions:

1. We strengthen Steinberger result and show that any Santha-Vazirani source with bias $\beta < 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. That is, the exact same result holds for a much more general class of sources.

2. We tighten Aaronson result and show that a depth d, size s Boolean circuit cannot solve the coin problem for $\beta < O(1/(\log{s})^{d-1})$. Moreover, our proof technique is different and we believe that it is simpler and more natural.



ISSN 1433-8092 | Imprint