COMP 193-ALB Algorithmic Lower Bounds: Fun with Hardness Proofs

This class takes a practical approach to proving problems can't be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P != NP). We focus on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, we'll 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).

Topics include NP-completeness (3SAT and all its variations, 3-partition, Hamiltonicity, 2D/3D geometric problems); PSPACE, EXPTIME, EXPSPACE; Games, Puzzles, and Computation (Tetris, Nintendo games: Super Mario Bros., The Legend of Zelda, Metroid, Pok?mon, ..., sliding blocks and Rush Hour, Constraint Logic, Sudoku and other Nikoli pencil-and-paper games, Chess, Go, Othello, and other board games); Inapproximability (PCP theorem and OPT-preserving reductions, APX-hardness e.g. Vertex Cover, set-cover hardness, group Steiner tree, k-dense subgraph, label cover and Unique Games Conjecture, Independent set); fixed-parameter intractability (parameter-preserving reductions, W hierarchy, clique-hardness); 3SUM-hardness (n^2 and the Exponential Time Hypothesis); counting problems (#P); solution uniqueness (ASP); game theory (PPAD); existential theory of the reals; undecidability.