Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications

Virginia Vassilevska Williams, Yinzhan Xu

TL;DR

This paper breaks new ground in fine-grained complexity by providing the first "truly subcubic" algorithm for the Min-Plus matrix product under a significantly relaxed set of structural constraints. By showing that matrices "close" to low-rank blocks can be multiplied in $O(n^{3-\epsilon})$ time, the authors unlock faster algorithms for fundamental problems like All-Pairs Shortest Paths (APSP) in geometric graphs, the Batch Range Mode problem, and the Maximum Subarray problem.

What Problem Does This Paper Address?

In computer science, the All-Pairs Shortest Paths (APSP) problem is a classic. For a graph with $n$ nodes, the standard Floyd-Warshall algorithm takes $O(n^3)$ time. While slight improvements exist, finding a "truly subcubic" algorithm—one running in $O(n^{3-\epsilon})$ for a constant $\epsilon > 0$—is a major open challenge.

APSP is computationally equivalent to the Min-Plus Product of two matrices (also known as the Distance Product). Because a general subcubic Min-Plus product remains elusive (leading to the "APSP Hypothesis"), researchers look for "structured" matrices where subcubic time is possible. Previously, this required matrices to have very small integer entries or "bounded differences" (where adjacent entries don't change much).

This paper asks: How much structure do we actually need? The authors aim to push the boundary toward "less structured" matrices that still allow for subcubic multiplication.

Methods

The authors introduce a new structural condition called $W$-approximate rank. A matrix has $W$-approximate rank $d$ if there exists a rank-$d$ matrix where every corresponding entry differs by at most $W$.

Their core contribution is a three-phase framework that builds upon and improves previous work by Bringmann et al.:

  1. Approximation via Geometry: They treat matrix entries as points and vectors in $d$-dimensional space. By using efficient geometric data structures for halfspace intersection reporting, they compute an additive approximation of the Min-Plus product.
  2. Random Sampling: They use random sampling of rows and columns to create a refined estimate matrix. Unlike previous methods that capped entries in both matrices, this approach only caps entries in one, offloading more work to this phase to simplify the final correction.
  3. Geometric Correction: They use the geometric data structure again to efficiently find and "correct" the specific triples $(i, k, j)$ that were missed in the previous phases but actually contribute to the true minimum.

Datasets

As a theoretical paper in algorithms and complexity, no empirical datasets were used. The results are proven mathematically for general classes of integer matrices satisfying the defined structural properties.

Key Insights and Ideas

  • Geometry Meets Algebra: The most striking insight is the reduction of an algebraic problem (Min-Plus product) to a geometric one (halfspace queries). If a matrix block is near low-rank, its rows/columns can be mapped to low-dimensional points, making geometric search tools viable.
  • Structure is a Spectrum: The paper shows that "bounded difference" matrices (the previous state-of-the-art) are just a specific, restricted case of $W$-approximate rank matrices. This generalization suggests that many "naturally occurring" matrices in various problems possess enough hidden structure to bypass the $O(n^3)$ barrier.
  • Breaking the Combinatorial Barrier: For the Batch Range Mode problem, the authors provide a non-combinatorial algorithm that beats the $O(n^{1.5})$ limit. This suggests that the perceived hardness of the problem was a limitation of "combinatorial" thinking rather than the problem itself.

Key Results

  • Main Theorem: They achieve a truly subcubic algorithm for $n \times n$ matrices where one matrix can be partitioned into blocks that are $W$-far from a constant rank matrix, provided $W$ isn't too large (roughly $O(n^{0.6})$).
  • Batch Range Mode: They provide the first $O(n^{1.4854})$ algorithm, breaking the $O(n^{1.5})$ barrier that was previously thought to be a hard limit for combinatorial approaches.
  • Maximum Subarray: They present the first subcubic algorithm for the 2D Maximum Subarray problem for matrices with entries as large as $O(n^{0.62})$.
  • Conditional Hardness: They prove that for $d$-dimensional Maximum Subarray, the existing "Kadane’s algorithm" is likely optimal ($n^{2d-1}$ time) under the Max-Weight Clique hypothesis, providing a tight lower bound for higher dimensions.

Limitations and Future Work

  • The "APSP Hypothesis" Still Stands: The algorithm still requires some structure. A truly subcubic algorithm for completely arbitrary, unstructured matrices remains the "holy grail" and is still out of reach.
  • Theoretical Exponents: The exponents achieved (like $n^{1.4854}$) are theoretically significant but involve the matrix multiplication constant $\omega \approx 2.373$. In practice, the overhead of the geometric data structures might make these algorithms slower than simpler ones for small to medium $n$.
  • Entry Size Bounds: While they increased the allowable size of matrix entries for the Maximum Subarray problem, there is still a polynomial bound. Extending this to arbitrary integers without a subcubic APSP algorithm would be a massive breakthrough.

Summary updated

Abstract

The goal of this paper is to get truly subcubic algorithms for Min-Plus product for less structured inputs than what was previously known, and to apply them to versions of All-Pairs Shortest Paths (APSP) and other problems. The results are as follows: (1) Our main result is the first truly subcubic algorithm for the Min-Plus product of two $n\times n$ matrices $A$ and $B$ with $\text{polylog}(n)$ bit integer entries, where $B$ has a partitioning into $n^{\epsilon}\times n^{\epsilon}$ blocks (for any $\epsilon>0$) where each block is at most $n^\delta$-far (for $\delta<3-\omega$, where $2\leq \omega<2.373$) in $\ell_\infty$ norm from a constant rank integer matrix. This result presents the most general case to date of Min-Plus product that is solvable in truly subcubic time. (2) The first application of our main result is a truly subcubic algorithm for APSP in a new type of geometric graph. Our result extends the result of Chan'10 in the case of integer edge weights by allowing the weights to differ from a function of the end-point identities by at most $n^\delta$ for small $\delta$. (3) In the second application we consider a batch version of the range mode problem in which one is given a length $n$ sequence and $n$ contiguous subsequences, and one is asked to compute the range mode of each subsequence. We give the first $O(n^{1.5-\epsilon})$ time for $\epsilon>0$ algorithm for this batch range mode problem. (4) Our final application is to the Maximum Subarray problem: given an $n\times n$ integer matrix, find the contiguous subarray of maximum entry sum. We show that Maximum Subarray can be solved in truly subcubic, $O(n^{3-\epsilon})$ (for $\epsilon>0$) time, as long as the entries are no larger than $O(n^{0.62})$ in absolute value. We also improve all the known conditional hardness results for the $d$-dimensional variant of Maximum Subarray.
BibTeX
@inproceedings{williams2020truly,
  author = {Virginia Vassilevska Williams and Yinzhan Xu},
  title = {{Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications}},
  booktitle = {SODA},
  year = {2020},
  url = {https://openreview.net/forum?id=owtfweoI4v},
}

Loading related content...

Figure