Tight Space Complexity of the Coin Problem

Mark Braverman, Sumegha Garg, Or Zamir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
PublisherIEEE Computer Society
Pages1068-1079
Number of pages12
ISBN (Electronic)9781665420556
DOIs
StatePublished - 2022
Event62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States
Duration: Feb 7 2022Feb 10 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2022-February
ISSN (Print)0272-5428

Conference

Conference62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Country/TerritoryUnited States
CityVirtual, Online
Period2/7/222/10/22

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • amplification
  • branching program
  • coin problem
  • complexity
  • lower bounds

Fingerprint

Dive into the research topics of 'Tight Space Complexity of the Coin Problem'. Together they form a unique fingerprint.

Cite this