New Unconditional Lower Bounds for Algorithms and Enumeration Problems
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Shows a matching lower bound for Scott and Sorkin’s max-2-CSP branching algorithm by building explicit graphs that force the LP/measure-and-conquer branching proportions from the dual, proving the cubic case runs in 2^{m/6} for cubic instances and that this yields the known 2^{0.19m} barrier for general instances (polynomial-space global separators can shave it to ~2^{0.18m}). Also gives tight enumeration lower bounds like 3^{n/3} maximal independent sets and extends constructions to minimal separators and hitting sets.
AI-written summary · about
chapters (7)
- 0:00Start
- 3:27Best Upper Bounds
- 4:19Polynomial Space Algorithms
- 11:38Type Constraints
- 21:57Enumeration Algorithms
- 23:14Enumeration of Maximal Independent Sets
- 26:45Minimal Separator
related talks
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
18mCharacterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
01h 31mCircuits of Bounded Depth