### 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.