Lower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Shows concrete conditional lower bounds for graph completion problems by tracing reductions from Gap 3SAT through Gap Max Cut and Optimum Linear Arrangement into chain completion and then into chordal/interval completions using a subdivide gadget and a chain-of-expanders to keep degree bounded. Under ETH it rules out 2^{o(√n / polylog n)} algorithms for sparse chordal completion, yielding roughly k^{1/4} lower bounds under ETH, while under a Gap Min‑Bisection hypothesis the paper proves no 2^{o(√k)} algorithms, using PCPs, the sparsification/specification lemma and careful expander constructions.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:31Motivation
- 2:50The square root phenomenon
- 6:11Known reductions
- 7:50OPTIMUM LINEAR ARRANGEMENT
- 10:31Reduction MAXCUT-OLA
- 14:08Hardness of GAP MAXCUT
- 17:35Reduction of Yannakakis
- 22:36Issues
- 23:28Hypothesis
- 25:29Reduction MINBISECTION OLA
- 27:13Conclusions
related talks
23mWorst-Case to Expander-Case Reductions
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
01h 32mInapproximability of Constraint Satisfaction Problems I
25mExponential separations using guarded extension variables
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
19mA Formal Disproof of Hirsch Conjecture
01h 31mCircuits of Bounded Depth
18mCharacterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly