Tight Space Complexity of the Coin Problem

Explore a comprehensive lecture on the tight space complexity of the coin problem presented by Sumegha Garg from Stanford University at the Simons Institute. Delve into the streaming space complexity of distinguishing between coins with different probabilities of landing heads. Examine the statistical solvability threshold and previous results showing the necessity of polynomial width for certain bias values. Learn about the closure of the gap between known bounds, revealing a tight threshold for when logarithmic width suffices versus when polynomial width is required. Discover the low-width construction for detecting biases greater than n^(-1/3) based on recursive majority. Gain insights into new combinatorial techniques used to analyze success probabilities in read-once branching programs for the lower bound proof. Understand the collaborative efforts with Mark Braverman and Or Zamir in advancing our understanding of this fundamental problem in computational complexity theory.

Tight Space Complexity of the Coin Problem