6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs


Graduate H-Level
Units: 3-0-9
Prerequisites: 6.046 (or equivalent), or permission of instructor
Instructor:  Prof. Erik Demaine (edemaine@mit.edu)
Schedule:  TR3:30-5, room 34-303
This subjects qualifies as a Theoretical Computer Science concentration subject or be counted as an AUS.
Techniques, tools, and tricks for proving lower bounds on algorithmic problems.  Reductions, gadgets.  Hardness/completeness in NP, PSPACE, EXPTIME, EXPSPACE, #P (counting), ASP (solution uniqueness), PPAD (game theory), 3SUM (n^2).  Undecidability, inapproximability (e.g. APX), and fixed-parameter intractability (e.g. W[1]).  3SAT, clique, set cover, label cover, and unique game hardness.  Games and puzzles.