MIT 6.890 Algorithmic Lower Bounds, Fall 2014 - Page 1

MIT 6.890 Algorithmic Lower Bounds, Fall 2014

MIT 6.890 Algorithmic Lower Bounds, Fall 2014

MIT OpenCourseWare

23 videos

91,154 views

Last updated

1:17:31

1. Overview

MIT OpenCourseWare

1:23:35

2. 3-Partition I

MIT OpenCourseWare

1:20:58

3. 3-Partition II

MIT OpenCourseWare

1:20:32

4. SAT I

MIT OpenCourseWare

1:21:39

5. SAT Reductions

MIT OpenCourseWare

1:18:40

6. Circuit SAT

MIT OpenCourseWare

1:23:03

7. Planar SAT

MIT OpenCourseWare

1:21:08

8. Hamiltonicity

MIT OpenCourseWare

1:20:26

9. Graph Problems

MIT OpenCourseWare

1:18:35

10. Inapproximabililty Overview

MIT OpenCourseWare

1:20:08

11. Inapproximability Examples

MIT OpenCourseWare

1:22:54

12. Gaps and PCP

MIT OpenCourseWare

1:21:13

13. W Hierarchy

MIT OpenCourseWare

1:22:49

14. ETH and Planar FPT

MIT OpenCourseWare

1:22:36

15. #P and ASP

MIT OpenCourseWare

1:18:17

16. NP and PSPACE Video Games

MIT OpenCourseWare

1:20:01

17. Nondeterministic Constraint Logic

MIT OpenCourseWare

1:20:38

18. 0- and 2-Player Games

MIT OpenCourseWare

1:22:38

19. Unbounded Games

MIT OpenCourseWare

1:23:22

20. Undecidable and P-Complete

MIT OpenCourseWare

1:19:23

21. 3SUM and APSP Hardness

MIT OpenCourseWare

1:20:48

22. PPAD

MIT OpenCourseWare

1:23:00

23. PPAD Reductions

MIT OpenCourseWare