Home » Course Layouts » Free Course Layout Udemy
6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2014, MIT OCW). Instructor: Professor Erik Demaine.
0
English
English [CC]
- Learn basic syntax that can apply to any language.
- Learn what is a programming language and the basic concepts for beginners.
- Understand what is Javascript in it's truest form.
- Know the basic syntax of Javascript.
- Know some hidden quirks in Javascript.
Description
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). (from ocw.mit.edu)
Course content
- Lecture 01 – Overview Unlimited
- Lecture 02 – 3-Partition I Unlimited
- Lecture 03 – 3-Partition II Unlimited
- Lecture 04 – SAT I Unlimited
- Lecture 05 – SAT Reductions Unlimited
- Lecture 06 – Circuit SAT Unlimited
- Lecture 07 – Planar SAT Unlimited
- Lecture 08 – Hamiltonicity Unlimited
- Lecture 09 – Graph Problems Unlimited
- Lecture 10 – Inapproximability Overview Unlimited
- Lecture 11 – Inapproximability Examples Unlimited
- Lecture 12 – Gaps and PCP Unlimited
- Lecture 13 – W Hierarchy Unlimited
- Lecture 14 – ETH and Planar FPT Unlimited
- Lecture 15 – #P and ASP Unlimited
- Lecture 16 – NP and PSPACE Video Games Unlimited
- Lecture 17 – Nondeterministic Constraint Logic Unlimited
- Lecture 18 – 0- and 2-Player Games Unlimited
- Lecture 19 – Unbounded Games Unlimited
- Lecture 20 – Undecidable and P-Complete Unlimited
- Lecture 21 – 3SUM and APSP Hardness Unlimited
- Lecture 22 – PPAD Unlimited
- Lecture 23 – PPAD Reductions Unlimited
Instructor
