Tight Space Complexity of the Coin Problem

on YouTube ↗52m

" summary

Proves a sharp threshold at c=1/3: read-once branching programs with effective width 1 and recursive AND–OR/majority gadgets achieve O(log n) width to detect bias β ≳ n^{−1/3} (construction uses a length r^{3/2} integer sequence that gives √r bias amplification). New combinatorial analysis of success-probability progression shows the converse: for β ≲ n^{−1/3} any read-once branching program needs polynomial width, so the construction is essentially tight.

AI-written summary · about

" chapters (14)

1. 0:00Tight Space Complexity of the Coin Problem
2. 1:20Optimal Distinguisher
3. 2:22Related Work
4. 3:00Low-Memory Distinguishers?
5. 5:32Hardness of the Coin Problem
6. 7:19Outline
7. 9:08Read-Once Branching Program (ROBP)
8. 12:25Coin Problem in ROBPS
9. 17:50Teaser: Tribes Function [BV'10]
10. 18:40ROBP for Tribes Function [BV'10]
11. 21:02Recursive Tribes [BV'10]
12. 26:24High-level Idea for the Simulation
13. 32:52Gadget for Upper Bound
14. 44:13Sequences Capturing Random Walks