Abstract
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 [BGW’20]).
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 of [Val'84]).
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 analyze progression of the success probabilities in read-once
branching programs.
Joint work with Mark Braverman and Or Zamir.