# 3SUM, All-Pairs Shortest Paths and Monochromatic Problems

Monday, March 9, 2020 1:45pm to 2:45pm

About this Event

29 Oxford Street, Cambridge, MA 02138

Two of the main hypotheses of Fine-Grained Complexity concern the 3SUM problem from Computational Geometry and the All-Pairs Shortest Paths (APSP) from Graph Algorithms; both are for the word RAM model of computation. The 3SUM hypothesis asserts that given a set A of n integers, any algorithm needs n^{2-o(1)} time to determine whether A contains 3 integers summing to 0. The APSP hypothesis says that given an n node graph G with integer weights bounded by poly(n), any algorithm needs n^{3-o(1)} time to compute the shortest paths distances between every pair of nodes of G.

Together with the Strong Exponential Time Hypothesis about the complexity of Boolean Satisfiability, these two hypotheses explain the best known running times for a huge variety of problems of interest. However, very little is known about how 3SUM and APSP relate to each other and whether their two hypotheses might be equivalent. In this talk we will discuss some relationships between the two problems. In particular, we will show that 3SUM is fine-grained equivalent to a problem called Monochromatic Convolution, and that both 3SUM and APSP are fine-grained reducible to a problem called Monochromatic Triangles. As both monochromatic problems merely ask about equality of colors (and no summations), these reductions show that the hardness of 3SUM and APSP is not due to having to sum large numbers as was originally believed.