Algorithmic Lower Bounds: Fun with Hardness Proofs
Massachusetts Institute of Technology via MIT OpenCourseWare
-
13
-
- Write review
Overview
Syllabus
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.
Taught by
Prof. Erik Demaine