Algorithmic Lower Bounds: Fun with Hardness Proofs

3-0-9 units · Graduate

A practical algorithmic approach to proving problems computationally hard for various complexity classes such as nondeterministic polynomial time (NP), polynomial space, exponential time, and recursively enumerable problems. Variety of hardness proof styles, reductions, and gadgets. Parsimonious reductions, hardness of approximation, counting solutions, and fixed-parameter algorithms. Connection between games and computation, with many examples drawn from games and puzzles.