Truly subcubic min-plus product for less structured matrices, with applications

Copyright © 2020 by SIAM 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 n3−o(1) time, and it is a big open problem whether a truly subcubic, O(n3−ε) 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 δ 0 for this problem can be used to solve Boolean matrix multiplication combinatorially in truly subcubic time. We give the first O(n1.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(n3−ε) (for ε > 0) time, as long as every entry of the input matrix is no larger than O(n0.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(n3−ε) 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