Subquadratic Time Matrix Multiplication Data Structures Beyond the Dual Exponent, with Applications
November 13, 2026 (1pm, GHC 8102 - part of the Theory Seminar series)

In the following matrix multiplication data structure problem, we preprocess an n by D matrix X and a D by n matrix Y, and then must answer queries (i,j) by returning the corresponding entries (XY)[i,j] of the matrix product. A solution is nontrivial if it has preprocessing time O(n^{2-delta}) (less than the size of the full product XY) and query time O(D^{1-epsilon}) (faster than brute force) for some constant delta,epsilon>0.

Prior work in fine-grained complexity showed that a variety of problems for which no improvements were known for decades can be reduced to such a data structure for various dimensions D. For instance, a data structure with the properties above for D=n^gamma for some gamma>0, however small, suffices to give a truly subquadratic algorithm for the 3SUM problem from computational geometry and a truly subcubic time algorithm for the All-Pairs Shortest Paths (APSP) problem from graph algorithms. Such a data structure was given by Alman and Vassilevska W., based on an algorithm developed by Anthropic that already refuted the longstanding APSP and 3SUM hypotheses.

Nevertheless, that data structure only works for middle dimension D