TY - GEN
T1 - Tight Space Complexity of the Coin Problem
AU - Braverman, Mark
AU - Garg, Sumegha
AU - Zamir, Or
N1 - 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 -