On the Subexponential Time Complexity of the CSP
summary
Detailed thresholds link structural parameters to sub-exponential solvability: if the number of tuples o(n) or the primal treewidth is sublinear then CSP is solvable in time domain^o(n), while linear tuples or treewidth rule out such algorithms under ETH; degree =1 is in P but ≥2 blocks sub-exponential algorithms; bounded-domain, bounded-arity CSP matches CNF-SAT equivalently under ETH; Boolean CSP with compressed tables yields strong hardness (solving it in sub-exponential time forces a Boolean compressed tables implies W2 collapse); CSP all-different reduces to list coloring giving a all-different → list-coloring 2^n algorithm and shows domain ≥3 is not sub-exponential under ETH; open case: linear number of constraints with linear domain remains unresolved.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:30Outline
- 1:08Problem Definition
- 2:19Restrictions & Structural Parameters
- 3:43Subexponential Time
- 4:43Our Work & Assumptions
- 5:47CNF-SAT and Boolean CSP
- 11:16Summary of the Results for CSP
- 12:35CSP with Global Constraints: Definitions
- 15:26Why Study CSP with Global Constraints?
- 21:03Highlight of the Results for CSP, CSPS, CSP2
- 22:24Open Questions
related talks
18mCharacterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly
01h 32mInapproximability of Constraint Satisfaction Problems I
23mWorst-Case to Expander-Case Reductions
25mExponential separations using guarded extension variables
34mNew Tools for Peak Memory Scheduling
01h 01mComplexity and Algorithmic Game Theory I
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
01h 31mCircuits of Bounded Depth