[+] OPTIONAL — 3SUM & APSP. kSUM upper and lower bounds, reductions. Distinct 3SUM, 3SUM′, GeomBase, 3 points on a line, point on 3 lines, Separator, Strips cover box, Triangles cover triangle, Hole in union, Triangle measure, Point covering, Visibility between segments, Visible triangle, Planar motion planning, 3D motion planning, fixedangle chains. Nonquadratic lower bounds for triangle finding. Conjectured cubic graph problems: diameter, allpairs shortest paths, negative triangle, radius, median.  
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^{2}) time to solve. It has been the basis for many “3SUMhardness” 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 3SUMhard, including a lot of computational geometry (where 3SUM originally comes from). We'll also talk about the generalization kSUM, which has fairly strong lower bounds assuming ETH, and the conjecturedcubic graph problems allpairs shortest paths and diameter. 
Handwritten notes, page 1/8 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/8 • [previous page] • [next page] • [PDF] 

Slides, page 1/13 •
[previous page] •
[next page] •
[PDF]
Figure drawn by Erik Demaine based on Figure 11 of http://dx.doi.org/10.1016/09257721(95)000222 Slides, page 1/13 • [previous page] • [next page] • [PDF] 