An Optimal Space Lower Bound for Approximating MAX-CUT
summary
Shows that in the single-pass streaming model any algorithm that beats a trivial factor-2 for MAX-CUT (specifically any 2−ε approximation for constant ε>0) requires linear space — sublinear o(n) space is impossible — with the quantitative lower bound worsening exponentially in 1/ε^2. The proof reduces to an implicit hidden partition communication problem built from T≈1/ε^2 random matchings, analyzes a hard bipartite vs random distribution, and proves the bound via Fourier techniques emphasizing L1 Fourier-convolution control and a component-growing intuition.
AI-written summary · about
chapters (21)
- 0:00Introduction
- 0:47Graph Problems
- 2:53MAXCUT
- 3:55Streaming
- 5:24Space Complexity
- 7:02Results
- 10:58Graphs
- 13:19Implicit Hidden Partition
- 15:36Distributional Version
- 16:00Graphical Representation
- 17:45Example
- 20:24Intuition
- 20:50Secures
- 22:03Examples
- 24:46The Simple Strategy
- 26:37The Adaptive Component
- 30:50Porting to a Lower Bound
- 34:17Component Growing Protocol
- 36:52Proof Plan
- 41:09Technical Contributions
- 43:43Summary