Lower Bounds on the Space Complexity of Dynamic Programming
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Proves a formal space lower bound for dynamic programming on tree decompositions by switching to a one-way read-only input Turing model and constructing ~k·3^k graphs with a fixed border X and a gadget that forbids exactly chosen colorings. Shows a tight 3^k space lower bound for 3‑coloring (matching known 3^k time lower bound) via a pigeonhole argument on machine configurations; similar constructions handle vertex cover and (with more complex gadgets) dominating set.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:44Dynamic Programming
- 2:28Tree Decomposition
- 4:52What is Dynamic Programming
- 5:35Formal Definition of Dynamic Programming
- 5:59Space Complexity Model
- 9:42Space Lower Bounds
- 17:04Force Coloring
- 18:27Boundary Graph
- 21:50What does it mean
- 22:20Lower Bounds
- 27:02The Big Question
- 27:32Optimal Running Time
- 29:39Future of space
- 30:43Dynamic Programming Algorithm
related talks
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
27mSuccinct Preferential Attachment Graphs
23mWorst-Case to Expander-Case Reductions
17mLifting to Parity Decision Trees Via Stifling
34mNew Tools for Peak Memory Scheduling
01h 31mCircuits of Bounded Depth
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
20mA Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems