ECCC-Report TR21-083https://eccc.weizmann.ac.il/report/2021/083Comments and Revisions published for TR21-083en-usMon, 21 Jun 2021 02:01:29 +0300
Paper TR21-083
| Tight Space Complexity of the Coin Problem |
Mark Braverman,
Sumegha Garg,
Or Zamir
https://eccc.weizmann.ac.il/report/2021/083In 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 $\frac{1}{2}+\beta$ from ones which are heads with probability $\frac{1}{2}-\beta$. We are interested in the 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 $\beta$ becomes smaller. Statistically, it can be solved whenever $\beta = \Omega(n^{-1/2})$, using counting. It has been previously shown that for $\beta = O(n^{-1/2})$, counting is essentially optimal (equivalently, width $poly(n)$ is necessary [Braverman-Garg-Woodruff FOCS'20]). On the other hand, the coin problem only requires $O(\log n)$ width for $\beta>n^{-c}$ for any constant $c>\log_2(\sqrt{5}-1)\approx 0.306$ (following low-width simulation of AND-OR tree of [Valiant Journal of Algorithms'84]).
In this paper, we close the gap between the bounds, showing a tight threshold between the values of $\beta=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 $\beta$.
We introduce new techniques in both bounds. For the upper bound, we give a construction based on recursive majority that does not require a memory stack of size $\log n$ bits. For the lower bound, we introduce new combinatorial techniques for analyzing progression of the success probabilities in read-once branching programs.Mon, 21 Jun 2021 02:01:29 +0300https://eccc.weizmann.ac.il/report/2021/083