# Algorithmic Lower Bounds: Fun with Hardness Proofs

- Institution: Massachusetts Institute of Technology
- Department: Electrical Engineering and Computer Science
- Teacher: Prof. Erik Demaine
- Term: Fall 2014
- Level: Graduate
- Language: English
- Subjects: Mathematics, Computer science, Engineering
- Source: [MIT OpenCourseWare](https://ocw.mit.edu/courses/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/)
- Licence: [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/) (Non-commercial use only.)
- Syllabus: [at the source](https://ocw.mit.edu/courses/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/pages/syllabus/)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs is a class taking a practical approach to proving problems can’t be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP). The class focuses on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, the class will create many interesting gadgets, learn many hardness proof styles, explore the connection between games and computation, survey several important problems and complexity classes, and crush hopes and dreams (for fast optimal solutions).

## Lectures

1. [Lecture 1: Overview](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/267fd470270c), 1 h 18 min (Video)
2. [Lecture 2: 3-Partition I](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/28e4cda2bae2), 1 h 24 min (Video)
3. [Lecture 3: 3-Partition II](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/f76f9d589769), 1 h 21 min (Video)
4. [Lecture 4: SAT I](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/68330d314d50), 1 h 21 min (Video)
5. [Lecture 5: SAT Reductions](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/c1c9227ca3eb), 1 h 22 min (Video)
6. [Lecture 6: Circuit SAT](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/e7e285f46cff), 1 h 19 min (Video)
7. [Lecture 7: Planar SAT](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/ae19574dddf6), 1 h 24 min (Video)
8. [Lecture 8: Hamiltonicity](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/598721ec235b), 1 h 22 min (Video)
9. [Lecture 9: Graph Problems](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/864130f4f5e3), 1 h 21 min (Video)
10. [Lecture 10: Inapproximabililty Overview](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/43fba9d8a5d2), 1 h 19 min (Video)
11. [Lecture 11: Inapproximability Examples](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/0ce0afab487a), 1 h 21 min (Video)
12. [Lecture 12: Gaps and PCP](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/e2b110d21b90), 1 h 23 min (Video)
13. [Lecture 13: W Hierarchy](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/232ac21d5807), 1 h 22 min (Video)
14. [Lecture 14: ETH and Planar FPT](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/be1cbd99ef91), 1 h 23 min (Video)
15. [Lecture 15: #P and ASP](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/ea79c4b8bd61), 1 h 23 min (Video)
16. [Lecture 16: NP and PSPACE Video Games](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/43839cb11cb0), 1 h 19 min (Video)
17. [Lecture 17: Nondeterministic Constraint Logic](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/fbb49afde4ad), 1 h 20 min (Video)
18. [Lecture 18: 0- and 2-Player Games](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/3c18c3a5192e), 1 h 21 min (Video)
19. [Lecture 19: Unbounded Games](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/ad86f2aab5fd), 1 h 23 min (Video)
20. [Lecture 20: Undecidable and P-Complete](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/2df8f304ee19), 1 h 24 min (Video)
21. [Lecture 21: 3SUM and APSP Hardness](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/a44a561efe0a), 1 h 20 min (Video)
22. [Lecture 22: PPAD](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/0aaaeca11b49), 1 h 21 min (Video)
23. [Lecture 23: PPAD Reductions](https://invisiblenetwork.ai/learn/mit/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/5845d3b5c89b), 1 h 23 min (Video)