In the coin problem we are asked to distinguish, with probability at least 2/3, between n i.i.d. coins which are heads with probability 1/2 + β from ones which are heads with probability 1/2 − β. We are interested in the streaming space complexity of the coin problem, corresponding to the width of a read-once branching program solving the problem.
The coin problem becomes more difficult as β becomes smaller. Statistically, it can be solved whenever β = Ω(n−1/2), using counting. It has been previously shown that for β =O(n−1/2), counting is essentially optimal (equivalently, width poly(n) is necessary).
On the other hand, the coin problem only requires O(log n) width for β >≈ n^{−0.3} (following low-width simulation of AND-OR tree).
In the paper, we close the gap between the bounds, showing a tight threshold between the values of β = n−c where O(log n) width suffices and the regime where poly(n) width is needed, with a transition at c = 1/3.
In this talk, we will first briefly discuss the low width construction for detecting biases β > n−1/3, which is based on recursive majority. Then we will focus on the lower bound that uses new combinatorial techniques to analyse progression of the success probabilities in read-once branching programs.
Joint work with Mark Braverman and Or Zamir.
This video was produced by the Simons Institute, and forms part of the workshop Structural Results.
