TY - GEN

T1 - Tight Space Complexity of the Coin Problem

AU - Braverman, Mark

AU - Garg, Sumegha

AU - Zamir, Or

N1 - Funding Information:
Email: sumegha.garg@gmail.com. Research supported by Michael O. Rabin Postdoctoral Fellowship.
Funding Information:
Email: mbraverm@cs.princeton.edu. Research supported in part by the NSF Alan T. Waterman Award, Grant No. 1933331, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry.
Publisher Copyright:
© 2022 IEEE.

PY - 2022

Y1 - 2022

N2 - 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 12}+β from ones which are heads with probability 12}-β. 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 β 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 [Braverman-Garg-Woodruff FOCS'20]). On the other hand, the coin problem only requires O(log n) width for β > n-c for any constant c > log2}(√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 β=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 β. 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.

AB - 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 12}+β from ones which are heads with probability 12}-β. 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 β 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 [Braverman-Garg-Woodruff FOCS'20]). On the other hand, the coin problem only requires O(log n) width for β > n-c for any constant c > log2}(√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 β=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 β. 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.

KW - amplification

KW - branching program

KW - coin problem

KW - complexity

KW - lower bounds

UR - http://www.scopus.com/inward/record.url?scp=85127132268&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85127132268&partnerID=8YFLogxK

U2 - 10.1109/FOCS52979.2021.00106

DO - 10.1109/FOCS52979.2021.00106

M3 - Conference contribution

AN - SCOPUS:85127132268

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 1068

EP - 1079

BT - Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021

PB - IEEE Computer Society

T2 - 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021

Y2 - 7 February 2022 through 10 February 2022

ER -