MIT 6.890 Algorithmic Lower Bounds, Fall 2014
In this lecture, Professor Demaine gives a brief overview of the class, summarizing the prerequisite complexity theory and featuring two examples of hardness proofs in games. Created by MIT OpenCourseWare .
Pick a lesson
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