6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs (Spring 2019)

This lecture is about strong lower bounds on running time that are possible by assuming the Exponential Time Hypothesis: there is no 2^o(n) algorithm to solve n-variable 3SAT. This conjecture is a stronger form of P ≠ NP, and it lets us keep track of “problem size blow-up”, something we've ignored before in our NP-hardness reductions. Many of the reductions we've seen, such as 3-coloring, vertex cover, dominating set, Hamiltonicity, and Independent Set/Clique have linear blow-up, so we get 2^o(n) lower bounds. On the other hand, planar versions of these problems (except Clique) have quadratic blow up because of the crossover gadgets, so we get 2^{o(√n) lower bounds.}

In parameterized complexity, we get a particularly strong form of FPT ≠ W[1]: there is no f(k) n^o(k) algorithm for Clique/Independent Set, for any computable function f. In particular, there's no f(k) n^O(1) (FPT) algorithm. By keeping track of the parameter blowup in our parameterized reductions, we can prove similar bounds for other problems, e.g. multicolored Clique/Independent Set, Dominating Set, Set Cover, and Partial Vertex Cover.

Finally, we'll cover a useful base problem, called Grid Tiling, for proving W[1]-hardness of problems on planar graphs or in 2D. Specifically, we'll use Grid Tiling to prove Scattered Set is W[1]-hard in planar graphs, and that Independent Set is W[1]-hard in in unit-disk graphs. These results also imply that these problems have no EPTAS.

This class, we don't have any assigned lecture videos (or new lecture material), but we'll still bring a bunch of fun problems in complexity.

Alas, this week's class will be the last one in which we solve problems! We have a bunch more new open problems, including a lot of fun video games. (No solved problems this week; if you don't want to work on open problems, work on your project!) In addition, I'll present the 1-page slide summaries of the presentations to come in the final two class sessions.