Algorithmic Lower Bounds (Fall 2014) (M-I-T)

• 1. Overview (M-I-T)
• 3. 3-Partition II (M-I-T)
• 4. SAT I (M-I-T)
• 5. SAT Reductions (M-I-T)
• 6. Circuit SAT (M-I-T)
• 7. Planar SAT (M-I-T)
• 8. Hamiltonicity (M-I-T)
• 9. Graph Problems (M-I-T)
• 10. Inapproximabililty Overview (M-I-T)
• 11. Inapproximability Examples (M-I-T)
• 12. Gaps and PCP (M-I-T)
• 13. W Hierarchy (M-I-T)
• 14. ETH and Planar FPT (M-I-T)
• 15. #P and ASP (M-I-T)
• 16. NP and PSPACE Video Games (M-I-T)
• 17. Nondeterministic Constraint Logic (M-I-T)
• 18. 0- and 2-Player Games (M-I-T)
• 19. Unbounded Games (M-I-T)
• 20. Undecidable and P-Complete (M-I-T)
• 21. 3SUM and APSP Hardness (M-I-T)
• 22. PPAD (M-I-T)
• 23. PPAD Reductions (M-I-T)