Simulating Branching Programs with Edit Distance and Friends
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Proves a concrete reduction from BP-SAT to LCS/edit distance: satisfiability of nondeterministic branching programs (width w, length T on n variables) maps to LCS or edit-distance on binary sequences of length about 2^{n/2}·poly(T,w). Builds recursive reachability gadgets (exponential in recursion depth k, k ≈ log T so final gadgets are polynomial in T for poly-length programs) that force LCS value iff a path exists. Consequence: truly subquadratic algorithms would yield 2^{n(1−ε)} SAT algorithms and new circuit lower bounds.
AI-written summary · about
chapters (17)
- 0:00Intro
- 1:48Edit Distance
- 3:45SETH Lower bounds
- 5:05How Strong is SETH?
- 9:40A hierarchy of SAT Problems
- 10:47Branching Programs (BPs)
- 13:14Main Result: A reduction
- 14:22The Expressibility of Branching Programs
- 16:06The Circuit Lower Bounds Barrier
- 19:20Mildly Subquadratic Algorithms
- 22:08Even more fine-grained
- 27:34The Connecting-Pair Problem?
- 31:31Reachability Gadgets
- 36:39Main Gadget: Why it works
- 38:37The Base Case: k=0
- 41:41Tighter Connections?
- 42:51The New P