Sparsification Lemma and ETH
summary
Describes a concrete tool: the sparsification lemma that rewrites any k‑CNF, in 2^{εn} time, as a disjunction of linearly many linear‑size k‑CNFs while preserving satisfiability, enabling reductions that preserve the variable parameter and thus transfer subexponential algorithms between many SNP problems. States ETH as s3>0 and studies the constants S_k (their S_k sequence), showing they rise infinitely often, conjecturing lim S_k = 1 and deriving conditional lower bounds and tight‑form consequences for parameterized and fine‑grained problems.
AI-written summary · about
chapters (11)
- 0:00Intro
- 2:58Exact Algorithms and Complexity
- 6:04Improved Exact Algorithms
- 7:17Improved Algorithms for HAMILTONIAN PATH
- 9:28Exact Complexity - Motivating Questions
- 12:29Connections between Problems
- 14:18Sparsification Lemma
- 22:44Exponential-time Hypothesis (ETH)
- 26:10Explanatory Value of ETH
- 37:45SETH - Strong Exponential Time Hypothesis
- 43:59Open Problems
related talks
29mImproved Deterministic Algorithms for Sparse Max-SAT
17mSatisfiability Algorithms Based on Concentrated Shrinkage
25mLower Bounds for Problems Parameterized by Clique-width
17mFrom Channel Assignment to Subgraph Isomorphism
29mEquality, Revisited
10mQuery, Communication and Discrepancy
29mAmplifying Contextual Distance in Higher-Order Languages, using the Law of Large Numbers
35mWhy Extension-Based Proofs Fail