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
DESCRIPTION
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/.
