6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs


Graduate H-Level
Units: 3-0-9
Prerequisites: 6.046 or 6.006
Instructor:  Prof. Erik Demaine (edemaine@mit.edu)
Schedule:  Lectures Wednesdays 7-9:30, room 32-082; Problem solving session Thursdays 7-9, room 32-082
This subjects qualifies as a Theoretical Computer Science concentration subject and also an II subject.
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. See more information at http://courses.csail.mit.edu/6.892/spring19/.