文章基本信息

标题：Tight Space Complexity of the Coin Problem
本地全文：下载
作者：Mark Braverman ; Sumegha Garg ; Or Zamir 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In the coin problem we are asked to distinguish, with probability at least 23 , between n iid coins which are heads with probability 21+ from ones which are heads with probability 21− . 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−12) , using counting. It has been previously shown that for =O(n−12) , 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(logn) width for n−c for any constant clog2(5−1)0306 (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(logn) width suffices and the regime where poly(n) width is needed, with a transition at c=13 . 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 logn bits. For the lower bound, we introduce new combinatorial techniques for analyzing progression of the success probabilities in read-once branching programs.
关键词：bias amplification;coin problem;majority;read-once branching programs;tight space bounds