Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly
summary
Claim: p pass streaming algorithms need space Theta(n^{deg(f)}) to compute Max‑CSPf exactly where deg(f) is f's multilinear polynomial degree and p is polylogarithmic Passes. Proof sketch: reduce any f to an AND on deg(f) variables via linear combinations of f clauses then prove AND (or OR) requires n^{k} space by a disjointness reduction from communication complexity. Approximation within 1 minus epsilon still requires nearly linear n^{1−o(1)} space.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 1:00Constraint Satisfaction Problems
- 3:08Streaming Algorithm
- 4:15The Problem
- 5:48Results
- 7:35Approach
- 13:07Solution
related talks
27mOn the Subexponential Time Complexity of the CSP
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
31mNew Unconditional Lower Bounds for Algorithms and Enumeration Problems
33mSub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse
33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
01h 02mFine-Grained Counting Complexity I
26mLower Bounds on the Running Time for Scheduling and Packing Problems
29mSubexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds