Prerequisites: 6.046 (or equivalent), or permission of instructor
Instructor: Prof. Erik Demaine (firstname.lastname@example.org)
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). 3SAT, clique, set cover, label cover, and unique game hardness. Games and puzzles.