Seminar Details

Given a sequence of n independent tosses of a coin biased towards either heads or tails with probability 1/2 + β, the aim of the coin problem is to determine which way the coin is biased. We study the space complexity of the coin problem in the streaming setting. This corresponds to quantifying 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 β = Ω(1/√n), using counting. We first show that for β = O(1/√n), counting is essentially optimal (equivalently, width poly(n) is necessary [BGW’20]) using an information-theoretic proof. An information-theoretic proof enables strengthening of the hardness result to solving multiple copies of the coin problem simultaneously.

On the other hand, the coin problem only requires O(log n) width for β > 1/n^{0.306} (following low-width simulation of AND-OR tree of [Val’84]). In the second paper [BGZ'21], using a combinatorial proof, 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. This gives a complete characterization (up to constant factors) of the memory complexity of solving the coin problem, for all values of bias β.
Joint works with Mark Braverman, David Woodruff and Or Zamir.