Exponential-Time Algorithms
summary
Survey of concrete exponential algorithms: branching recurrences give an Independent Set solver around 1.39^n and a simple 3‑coloring tweak knocks runtime to about 1.4^n (using the 1.89^n bound on maximal independent sets); local search (Schöning) yields roughly (4/3)^n; Bellman‑style dynamic programming solves Hamiltonian in 2^n time and 2^n space (or polynomial space at ~4^n); meet‑in‑the‑middle gives 2^{n/2} time/space, matrix multiplication reduces k‑clique to n^{ω·k/3}, and randomized algebraic fingerprinting plus polynomial identity testing yields ~1.66^n; overall emphasis on branching recurrences, meet‑in‑the‑middle, zeta transform.
AI-written summary · about
chapters (13)
- 0:00Intro
- 4:20Example: 3-colouring
- 7:02Example: Hamiltonicity, degree 3
- 17:16Example: Independent Set
- 19:03Example: Vertex Colouring
- 23:31Example: Satisfiability for 3CNF
- 28:55Example: Laplace Expansion
- 33:53Example: Colouring
- 39:31Sum of 2 Sets of Vectors
- 40:58Example: Exact CNF Sat
- 44:12Counting Triangles
- 46:17Example: k-Clique
- 49:12Polynomial Identity Testing
related talks
31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
25mLower Bounds for Problems Parameterized by Clique-width
23mTowards General and Tight Hardness Results for Graph Problems
19mDeterministic Dynamic Matching In Worst-Case Update Time
29mImproved Deterministic Algorithms for Sparse Max-SAT
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
39mSketching and Randomization for Distributed Submodular and Coverage Optimization
01h 21mComputational Complexity in Theory and in Practice