Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Describes sub-exponential approximation schemes for constraint satisfaction problems (CSPs) that extend techniques from dense instances to ones that are almost sparse. Focuses on algorithmic approaches achieving sub-exponential time approximations for CSPs across a spectrum of instance densities, identifying how performance degrades as sparsity increases.
AI-written summary · about
chapters (5)
related talks
18mCharacterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly
01h 32mInapproximability of Constraint Satisfaction Problems I
25mExponential separations using guarded extension variables
23mWorst-Case to Expander-Case Reductions
34mNew Tools for Peak Memory Scheduling
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
01h 31mCircuits of Bounded Depth