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

The All-Pairs Shortest Paths (APSP) problem is one of the most basic problems in computer science. The fastest known algorithms for APSP in n-node graphs run in n 3-o(1) time, and it is a big open problem whether a truly subcubic, O(n 3-ε ) for ε > 0 time algorithm exists for APSP. The Min-Plus product of two n × n matrices is known to be equivalent to APSP, where the optimal running times of the two problems differ by at most a constant factor. A natural way to approach understanding the complexity of APSP is thus understanding what structure (if any) is needed to solve Min-Plus product in truly subcubic time. 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 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 × n matrices A and B with polylog n bit integer entries, where B has a partitioning into n ε × n ε blocks (for any ε > 0) where each block is at most n δ -far (for δ < 3 -ω, where 2 ≤ ω < 2.373) in ℓ ∞ norm from a constant rank integer matrix. This result presents the most general case to date of Min-Plus product that is still 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. Chan'10 solved APSP in truly subcubic time in geometric graphs whose edges have weights that are a function of the identities of the edge's end-points. Our result extends Chan's result 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 δ for small δ.

(3) In a second application we consider a batch version of the range mode problem in which one is given a sequence of numbers a 1 , . . . , a n and n intervals defining contiguous subsequences, and one is asked to compute the range mode of each subsequence. Chan et al.'14 showed that any O(n 1.5-ε ) time combinatorial algorithm for ε > 0 for this problem can be used to solve Boolean matrix multiplication combinatorially in truly subcubic time. We give the first O(n 1.5-ε ) time for ε > 0 algorithm for this batch range mode problem, showing that the hardness is indeed constrained to combinatorial algorithms.

(4) Our final application is to the Maximum Subarray problem: given an n × 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-ε ) (for ε > 0) time, as long as every entry of the input matrix is no larger than O(n 0.62 ) in absolute value. This is the first truly subcubic algorithm for an interesting case of Maximum Subarray. The Maximum Subarray problem with arbitrary integer entries is known to be subcubically equivalent to APSP, in that a truly subcubic, O(n 3-ε ) time algorithm for ε > 0 for one problem would imply a truly subcubic algorithm for the other. Because of this it is believed that Maximum Subarray does not admit truly subcubic algorithms, without a restriction on the inputs.

We also improve all the known conditional hardness results for the d-dimensional variant of Maximum Subarray, showing that many of the known algorithms are likely tight.