Erik Demaine
Algorithmic Lower Bounds — twenty-three lectures from MIT, Fall 2014.Algorithmic Lower Bounds. Twenty-three lectures from MIT’s Fall 2014 course: Overview, 3-Partition I, 3-Partition II, SAT I, SAT Reductions and Circuit SAT.
Algorithmic Lower Bounds · 23 lectures
1: Overview
2: 3-Partition I
3: 3-Partition II
4: SAT I
5: SAT Reductions
6: Circuit SAT
7: Planar SAT
8: Hamiltonicity
9: Graph Problems
10: Inapproximabililty Overview
11: Inapproximability Examples
12: Gaps and PCP
13: W Hierarchy
14: ETH and Planar FPT
15: #P and ASP
16: NP and PSPACE Video Games
17: Nondeterministic Constraint Logic
18: 0 - and 2-Player Games
19: Unbounded Games
20: Undecidable and P-Complete
21: 3SUM and APSP Hardness
22: PPAD
23: PPAD Reductions