6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)

This lecture is about hardness of problems that can be solved in polynomial time but where that polynomial seems to be substantially superlinear. Our focus will be on 3SUM (given n integers, do any 3 sum to zero?) which is conjectured to require roughly Θ(n²) time to solve. It has been the basis for many “3SUM-hardness” reductions, so if any of the problems can be solved in O(n^2 − ε) time, then so can 3SUM. In class, we'll prove many problems 3SUM-hard, including a lot of computational geometry (where 3SUM originally comes from). We'll also talk about the generalization k-SUM, which has fairly strong lower bounds assuming ETH, and the conjectured-cubic graph problems all-pairs shortest paths and diameter.