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

Virginia Vassilevska Williams, Yinzhan Xu

Abstract

This paper presents the first truly subcubic algorithms for the Min-Plus matrix product under significantly relaxed structural constraints. Specifically, we address $n \times n$ matrices where blocks are $n^\delta$-far in $\ell_\infty$ norm from a constant rank integer matrix. This advancement enables truly subcubic solutions ($O(n^{3-\epsilon})$) for several fundamental problems. Key applications include a new algorithm for All-Pairs Shortest Paths (APSP) in geometric graphs, the first $O(n^{1.5-\epsilon})$ time algorithm for the Batch Range Mode problem, and a subcubic solution for the 2D Maximum Subarray problem with entries up to $O(n^{0.62})$. Additionally, we provide improved conditional hardness results for the $d$-dimensional Maximum Subarray problem.

Introduction

The All-Pairs Shortest Paths (APSP) problem is a cornerstone of graph theory. While the standard Floyd-Warshall algorithm operates in $O(n^3)$ time, the search for a "truly subcubic" algorithm—one running in $O(n^{3-\epsilon})$ for a constant $\epsilon > 0$—remains one of the most significant challenges in fine-grained complexity.

APSP is computationally equivalent to the Min-Plus Product (or Distance Product) of two matrices. Given the "APSP Hypothesis," which suggests that a truly subcubic algorithm for general Min-Plus product may not exist, researchers have focused on identifying specific matrix structures that allow for faster computation. Previous breakthroughs required matrices to have very small integer entries or "bounded differences." This paper pushes these boundaries, exploring how much structure is truly necessary to bypass the cubic barrier.

Defining "Less Structured" Matrices

The authors introduce a generalized structural condition termed $W$-approximate rank. A matrix $B$ is said to have $W$-approximate rank $d$ if it can be partitioned into blocks that are at most $W$-far (in $\ell_\infty$ norm) from a constant rank-$d$ integer matrix.

This definition is a significant generalization of previous models. For instance, "bounded difference" matrices—where adjacent entries change by a small constant—are merely a restricted subset of $W$-approximate rank matrices. By allowing entries to deviate by as much as $n^\delta$, the authors demonstrate that subcubic multiplication is possible for a much broader class of "naturally occurring" matrices than previously thought.

The Three-Phase Algorithmic Framework

The core of the paper is a sophisticated three-phase framework that reduces the algebraic Min-Plus product to a series of geometric problems:

  1. Geometric Approximation: The algorithm treats matrix entries as points and vectors in $d$-dimensional space. By utilizing efficient geometric data structures for halfspace intersection reporting, the authors compute an initial additive approximation of the Min-Plus product.
  2. Refined Random Sampling: Building on techniques by Bringmann et al., the authors use random sampling of rows and columns to refine the estimate. A key innovation here is the asymmetrical treatment of the matrices; by only capping entries in one matrix, they simplify the subsequent correction phase.
  3. Geometric Correction: The framework returns to geometric data structures to identify and "correct" specific triples $(i, k, j)$ that were missed in earlier phases but are essential for the true minimum. This phase ensures the algorithm is exact rather than just an approximation.

Key Applications

All-Pairs Shortest Paths in Geometric Graphs

The main result leads directly to a truly subcubic algorithm for APSP in a new class of geometric graphs. This extends previous work by allowing edge weights to deviate from a function of endpoint identities by a factor of $n^\delta$, providing more flexibility in modeling real-world spatial networks.

Breaking the Batch Range Mode Barrier

In the Batch Range Mode problem, one must find the most frequent element in $n$ different contiguous subsequences of a length $n$ sequence. Previously, it was widely believed that $O(n^{1.5})$ was a hard limit for combinatorial approaches. The authors provide a non-combinatorial algorithm running in $O(n^{1.4854})$ time, suggesting that the perceived difficulty was a limitation of combinatorial methods rather than the problem's inherent complexity.

Maximum Subarray Problem

The 2D Maximum Subarray problem asks for the contiguous subarray with the maximum sum of entries. The authors present the first subcubic algorithm for this problem for matrices with entries as large as $O(n^{0.62})$. Furthermore, they prove that for the $d$-dimensional variant, the existing $O(n^{2d-1})$ "Kadane’s algorithm" is likely optimal under the Max-Weight Clique hypothesis.

Conclusion and Future Work

This research significantly expands the landscape of problems solvable in truly subcubic time by bridging the gap between algebraic matrix products and geometric search. While the "APSP Hypothesis" for completely unstructured matrices still stands, this work shows that even a small amount of hidden structure—represented by $W$-approximate rank—is sufficient to break the $O(n^3)$ barrier.

Future research may focus on further increasing the allowable entry size for the Maximum Subarray problem or reducing the theoretical overhead of the geometric data structures to make these algorithms more practical for smaller datasets. The ultimate goal remains the discovery of a truly subcubic algorithm for arbitrary matrices, or a proof that such a feat is impossible.

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},
}
Figure