Streaming Lower Bounds for Approximating MAX-CUT
summary
Proves any single-pass streaming algorithm that beats a trivial 2-approximation for MAX-CUT (achieving 2−ε) requires Ω(√n) space, even when edges arrive in a random-order stream. Construction uses k ≈ 1/ε^2 independent sparse G(n,α/n) phases: the yes case shares a global bipartition, the no case resamples it each phase, creating a constant gap in MAX-CUT. Main techniques: k‑party → two‑party reduction to a Boolean hidden partition problem, Fourier‑analytic lower bounds and a birthday‑paradox random‑walk upper bound showing tightness for the distribution.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:43Streaming model
- 8:40Hard distribution
- 12:06Hard input distribution Partition the stream into k = 1/(az) phases
- 13:35k-party communication problem
- 16:15Boolean hidden partition problem (BHP)
- 19:23Distributional BHP (D-BHP)
- 21:19Reduction from D-BHP to MAX-CUT
- 24:21Communication complexity of D-BHP
- 25:56Stream of L.I.D. samples
- 27:20Open problems
related talks
59mRandom log(n)-CNF are Hard for Cutting Planes (Again)
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
01h 09mInformation Theory in Computational Complexity IV
52mThe Mystery of the Missing String
01h 17mInapproximability of Constraint Satisfaction Problems III
58mMarkov Chain Mixing Times and Applications III
01h 10mDistribution Estimation and Applications I
01h 02mMarkov Chain Mixing Times and Applications II