Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
The first polynomial improvements over the textbook algorithms for 3-SUM and All-Pairs Shortest Paths are given, and the Exact Triangle hypothesis is refuted, and the All-Edges Sparse Triangle problem is solved in truly subquadratic time on sparse lopsided tripartite graphs.