We give the first polynomial improvements over the textbook algorithms for 33SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve 33SUM on nn integers of polynomial size in O(n^{1.9992})O(n1.9992) time and APSP on directed nn-vertex graphs with polynomially bounded integer weights in O(n^{2.9995})O(n2.9995) time. This refutes the 33SUM and APSP hypotheses. Using known reductions, we also refute the real-valued versions of the 33SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight kk-Clique hypotheses, and the three rectangular hinted Online Matrix--Vector conjectures of van den Brand, Nanongkai, and Saranurak, and we give polynomial speedups for a variety of other problems.
All of these results follow from a single new algorithm for thin matrix products. Let XX be an N\times DN×D integer matrix and YY a D\times ND×N integer matrix with D\le N^{1/18}D≤N1/18, and let WW be any set of at most N^2/\sqrt DN2/D−−√ positions. We compute the entries (XY)［I,J］(XY)［I,J］, (I,J)\in W(I,J)∈W, in O(N^2/D^{0.063})O(N2/D0.063) operations, which is polynomially less than the time needed to write down XYXY or to compute N^2/\sqrt DN2/D−−√ inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Schönhage, to perform only the operations needed for the entries in WW, and show that few operations are needed. Interpreted as a graph algorithm, this solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs where two parts have nn vertices but one part has n^{\varepsilon}nε vertices for \varepsilon<0.12ε<0.12. By known reductions, Exact Triangle, and hence 33SUM and APSP, reduce to this problem. We also give a data structure version that answers queries for single entries of XYXY, not known in advance.
