Virginia Vassilevska Williams
R. Ryan Williams
Skip Abstract Section
Abstract
We say an algorithm on n × n matrices with integer entries in [−M,M] (or n-node graphs with edge weights from [−M,M]) is truly subcubic if it runs in O(n3 − δ ċ poly(log M)) time for some δ > 0. We define a notion of subcubic reducibility and show that many important problems on graphs and matrices solvable in O(n3) time are equivalent under subcubic reductions. Namely, the following weighted problems either all have truly subcubic algorithms, or none of them do:
•The all-pairs shortest paths problem on weighted digraphs (APSP).
•Detecting if a weighted graph has a triangle of negative total edge weight.
•Listing up to n2.99 negative triangles in an edge-weighted graph.
•Finding a minimum weight cycle in a graph of non-negative edge weights.
•The replacement paths problem on weighted digraphs.
•Finding the second shortest simple path between two nodes in a weighted digraph.
•Checking whether a given matrix defines a metric.
•Verifying the correctness of a matrix product over the (min, +)-semiring.
•Finding a maximum subarray in a given matrix.
Therefore, if APSP cannot be solved in n3−ε time for any ε > 0, then many other problems also need essentially cubic time. In fact, we show generic equivalences between matrix products over a large class of algebraic structures used in optimization, verifying a matrix product over the same structure, and corresponding triangle detection problems over the structure. These equivalences simplify prior work on subcubic algorithms for all-pairs path problems, since it now suffices to give appropriate subcubic triangle detection algorithms.
Other consequences of our work are new combinatorial approaches to Boolean matrix multiplication over the (OR,AND)-semiring (abbreviated as BMM). We show that practical advances in triangle detection would imply practical BMM algorithms, among other results. Building on our techniques, we give two improved BMM algorithms: a derandomization of the combinatorial BMM algorithm of Bansal and Williams (FOCS’09), and an improved quantum algorithm for BMM.
- Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. 2015. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 1681--1697. Google Scholar
Digital Library
- N. Alon. 2009. Personal communication.Google Scholar
- N. Alon, Z. Galil, and O. Margalit. 1997. On the exponent of the all-pairs shortest path problem. J. Comput. Syst. Sci. 54, 2 (1997), 255--262. Google ScholarDigital Library
- N. Alon and A. Naor. 2006. Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput. 35 (2006), 787--803. Google ScholarDigital Library
- Arne Andersson and Mikkel Thorup. 2007. Dynamic ordered sets with exponential search trees. J. ACM 54, 3 (2007), 13. Google ScholarDigital Library
- N. Bansal and R. Williams. 2009. Regularity lemmas and combinatorial algorithms. In Proceedings of the Symposium on Foundations of Computer Science (FOCS’09). 745--754. Google ScholarDigital Library
- Nikhil Bansal and Ryan Williams. 2012. Regularity lemmas and combinatorial algorithms. Theory Comput. 8, 1 (2012), 69--94.Google ScholarCross Ref
- I. Baran, E.D. Demaine, and M. Patrascu. 2008. Subquadratic algorithms for 3 SUM. Algorithmica 50, 4 (2008), 584--596.Google ScholarDigital Library
- Jon Bentley. 1984. Programming pearls: Algorithm design techniques. Commun. ACM 27, 9 (Sept. 1984), 865--873. Google ScholarDigital Library
- A. Bernstein. 2010. A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’10). 742--755. Google ScholarDigital Library
- M. Blum and S. Kannan. 1995. Designing programs that check their work. J. ACM 42, 1 (1995), 269--291. Google ScholarDigital Library
- J. Brickell, I. S. Dhillon, S. Sra, and J. A. Tropp. 2008. The metric nearness problem. SIAM J. Matrix Anal. Appl. 30, 1 (2008), 375--396. Google ScholarDigital Library
- H. Buhrman and R. Špalek. 2006. Quantum verification of matrix products. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06). 880--889. Google ScholarDigital Library
- T. M. Chan. 1999. Geometric applications of a randomized optimization technique. Discrete Comput. Geom. 22, 4 (1999), 547--567.Google ScholarCross Ref
- T. M. Chan. 2007. More algorithms for all-pairs shortest paths in weighted graphs. In Proceedings of the Symposium on Theory of Computing (STOC’07). 590--598. Google ScholarDigital Library
- Timothy M. Chan. 2010. More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput. 39, 5 (2010), 2075--2089.Google ScholarCross Ref
- Timothy M. Chan. 2015. Speeding up the four russians algorithm by about one more logarithmic factor. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 212--217. Google ScholarDigital Library
- Timothy M. Chan and Ryan Williams. 2016. Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’16). 1246--1255. Google ScholarDigital Library
- D. Coppersmith and S. Winograd. 1990. Matrix multiplication via arithmetic progressions. J. Symbol. Comput. 9, 3 (1990), 251--280. Google ScholarDigital Library
- A. Czumaj and A. Lingas. 2007. Finding a heaviest triangle is not harder than matrix multiplication. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’07). 986--994. Google ScholarDigital Library
- Artur Czumaj and Andrzej Lingas. 2009. Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication. SIAM J. Comput. 39, 2 (2009), 431--444. Google ScholarDigital Library
- A.M. Davie and A. J. Stothers. 2013. Improved bound for complexity of matrix multiplication. Proc. Roy. Soc. Edinburgh, Sec. A Math. 143 (4 2013), 351--369. Issue 02.Google Scholar
- M. Dietzfelbinger. 1996. Universal hashing and k-wise independent random variables via integer arithmetic without primes. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS’96). 569--580. Google ScholarDigital Library
- R. Duan and S. Pettie. 2009. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’09). 384--391. Google ScholarDigital Library
- D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press. Google ScholarDigital Library
- D. Dubois and H. Prade. 1980. Fuzzy Sets and Systems: Theory and Applications. Academic Press.Google Scholar
- D. Eppstein. 1998. Finding the k shortest paths. SIAM J. Comput. 28, 2 (1998), 652--673. Google ScholarDigital Library
- M. J. Fischer and A. R. Meyer. 1971. Boolean matrix multiplication and transitive closure. In Proceedings of the Symposium on Foundations of Computer Science (FOCS’71). 129--131. Google ScholarDigital Library
- R. W. Floyd. 1962. Algorithm : Shortest path. Comm. ACM 5 (1962), 345. Google ScholarDigital Library
- M. L. Fredman and R. E. Tarjan. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 3 (1987), 596--615. Google ScholarDigital Library
- R. Freivalds. 1977. Probabilistic machines can use less running time. Proceedings of the IFIP Congress. 839--842.Google Scholar
- A. M. Frieze and R. Kannan. 1999. Quick approximation to matrices and applications. Combinatorica 19, 2 (1999), 175--220.Google ScholarCross Ref
- A. Gajentaan and M. Overmars. 1995. On a class of O(n<sup>2</sup>) problems in computational geometry. Computational Geometry 5, 3 (1995), 165--185. Google ScholarDigital Library
- François Le Gall. 2014. Powers of tensors and fast matrix multiplication. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’14). 296--303. Google ScholarDigital Library
- J. Hershberger, S. Suri, and A. Bhosle. 2007. On the difficulty of some shortest path problems. ACM TALG 3, 1 (2007), 5. Google ScholarDigital Library
- A. Itai and M. Rodeh. 1978. Finding a minimum circuit in a graph. SIAM J. Comput. 7, 4 (1978), 413--423.Google ScholarDigital Library
- S. Jeffery, R. Kothari, and F. Magniez. 2012. Improving quantum query complexity of boolean matrix multiplication using graph collision. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP’12). 522--532. Google ScholarDigital Library
- D. Karger, D. Koller, and S. Phillips. 1993. Finding the hidden path: Time bounds for all-pairs shortest paths. SIAM J. Comput. 22, 6 (1993), 1199--1217. Google ScholarDigital Library
- N. Katoh, T. Ibaraki, and H. Mine. 1982. An efficient algorithm for K shortest simple paths. Networks 12, 4 (1982), 411--427.Google ScholarCross Ref
- E. L. Lawler. 1971/72. A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Manage. Sci. 18 (1971/72), 401--405.Google Scholar
- F. Le Gall. 2012. Improved output-sensitive quantum algorithms for Boolean matrix multiplication. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 1464--1476. Google ScholarDigital Library
- L. Lee. 2002. Fast context-free grammar parsing requires fast boolean matrix multiplication. J. ACM 49, 1 (2002), 1--15. Google ScholarDigital Library
- A. Lingas. 2009. A fast output-sensitive algorithm for boolean matrix multiplication. In Proceedings of the European Symposium on Algorithms (ESA’09). 408--419.Google ScholarCross Ref
- Andrzej Lingas. 2011. A fast output-sensitive algorithm for boolean matrix multiplication. Algorithmica 61, 1 (2011), 36--50.Google ScholarDigital Library
- F. Magniez, M. Santha, and M. Szegedy. 2005. Quantum algorithms for the triangle problem. In Proceedings of the Symposium on Discrete Algorithms (SODA’05). 1109--1117. Google ScholarDigital Library
- J. Matousek. 1991. Computing dominances in E<sup>n</sup>. Info. Process. Lett. 38, 5 (1991), 277--278. Google ScholarDigital Library
- J. I. Munro. 1971. Efficient determination of the transitive closure of a directed graph. Info. Process. Lett. 1, 2 (1971), 56--58. Google ScholarDigital Library
- V. Y. Pan. 1978. Strassen’s algorithm is not optimal; trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations. In Proceedings of the Symposium on Foundations of Computer Science (FOCS’78). 166--176. Google ScholarDigital Library
- V. Y. Pan. 1980. New fast algorithms for matrix operations. SIAM J. Comput. 9, 2 (1980), 321--342.Google ScholarDigital Library
- M. Patrascu. 2010. Towards polynomial lowed bounds for dynamic problems. In Proceedings of the Symposium on Theory of Computing (STOC’10). 603--610. Google ScholarDigital Library
- L. Roditty. 2007. On the -simple shortest paths problem in weighted directed graphs. In Proceedings of the Symposium on Discrete Algorithms (SODA’07). 920--928. Google ScholarDigital Library
- Liam Roditty. 2010. On the k shortest simple paths problem in weighted directed graphs. SIAM J. Comput. 39, 6 (2010), 2363--2376.Google ScholarDigital Library
- L. Roditty and U. Zwick. 2004. On dynamic shortest paths problems. In Proceedings of the European Symposium on Algorithms (ESA’04). 580--591.Google Scholar
- L. Roditty and U. Zwick. 2005. Replacement paths and k simple shortest paths in unweighted directed graphs. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP’05). 249--260. Google ScholarDigital Library
- Liam Roditty and Uri Zwick. 2012. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Trans. Algor. 8, 4 (2012), 33. Google ScholarDigital Library
- A. Shoshan and U. Zwick. 1999. All-pairs shortest paths in undirected graphs with integer weights. In Proceedings of the Symposium on Foundations of Computer Science (FOCS’99). 605--614. Google ScholarDigital Library
- J. P. Spinrad. 2003. Efficient graph representations. Fields Inst. Monogr. 19 (2003).Google Scholar
- A. Stothers. 2010. On the Complexity of Matrix Multiplication. Ph.D. Thesis, University of Edinburgh.Google Scholar
- V. Strassen. 1969. Gaussian elimination is not optimal. Numer. Math. 13 (1969), 354--356. Google ScholarDigital Library
- Hisao Tamaki and Takeshi Tokuyama. 1998. Algorithms for the maximum subarray problem based on matrix multiplication. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98). 446--452. Google ScholarDigital Library
- L. G. Valiant. 1975. General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10 (1975), 308--315. Google ScholarDigital Library
- V. Vassilevska. 2008. Nondecreasing paths in weighted graphs, or: How to optimally read a train schedule. In Proceedings of the Symposium on Discrete Algorithms (SODA’08). 465--472. Google ScholarDigital Library
- V. Vassilevska and R. Williams. 2006. Finding a maximum weight triangle in n<sup>3 − Δ</sup> time, with applications. In Proceedings of the Symposium on Theory of Computing (STOC’06). 225--231. Google ScholarDigital Library
- V. Vassilevska, R. Williams, and R. Yuster. 2006. Finding the smallest H-subgraph in real weighted graphs and related problems. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP’06). 262--273. Google ScholarDigital Library
- V. Vassilevska, R. Williams, and R. Yuster. 2007. All-pairs bottleneck paths for general graphs in truly sub-cubic time. In Proceedings of the Symposium on Theory of Computing (STOC’07). 585--589. Google ScholarDigital Library
- Virginia Vassilevska, Ryan Williams, and Raphael Yuster. 2009. All-pairs bottleneck paths and max-min matrix products in truly subcubic time. Theory Comput. 5, 1 (2009), 173--189.Google ScholarCross Ref
- Virginia Vassilevska, Ryan Williams, and Raphael Yuster. 2010. Finding heaviest H-subgraphs in real weighted graphs, with applications. ACM Trans. Algor. 6, 3 (2010). Google ScholarDigital Library
- Virginia Vassilevska Williams. 2010. Nondecreasing paths in a weighted graph or: How to optimally read a train schedule. ACM Trans. Algor. 6, 4 (2010). Google ScholarDigital Library
- S. Warshall. 1962. A theorem on boolean matrices. J. ACM 9, 1 (1962), 11--12. Google ScholarDigital Library
- R. Williams. 2007. Matrix-vector multiplication in sub-quadratic time (some preprocessing required). In Proceedings of the Symposium on Discrete Algorithms (SODA’07). 995--1001. Google ScholarDigital Library
- Ryan Williams. 2014. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the Symposium on Theory of Computing (STOC’14). 664--673. Google ScholarDigital Library
- Virginia Vassilevska Williams. 2012. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the 44th Symposium on Theory of Computing (STOC’12). 887--898. Google ScholarDigital Library
- G. J. Woeginger. 2008. Open problems around exact algorithms. Discrete Appl. Math. 156, 3 (2008), 397--405. Google ScholarDigital Library
- J. Y. Yen. 1970/71. Finding the K shortest loopless paths in a network. Manage. Sci. 17 (1970/71), 712--716.Google Scholar
- Huacheng Yu. 2015. An improved combinatorial algorithm for boolean matrix multiplication. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP’15). 1094--1105.Google ScholarCross Ref
- G. Yuval. 1976. An algorithm for finding all shortest paths using N<sup>2.81</sup> infinite-precision multiplications. Inf. Proc. Lett. 4 (1976), 155--156.Google ScholarCross Ref
- U. Zwick. 2002. All-pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49, 3 (2002), 289--317. Google ScholarDigital Library
Index Terms
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
Recommendations
Subcubic Equivalences between Path, Matrix and Triangle Problems
FOCS '10: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer ScienceWe say an algorithm on n by n matrices with entries in [-M, M] (or n-node graphs with edge weights from [-M, M]) is truly sub cubic if it runs in O(n^{3-\delta} \poly(\log M)) time for some \delta > 0. We define a notion of sub cubic reducibility, and ...
A Shortest Path Algorithm for Real-Weighted Undirected Graphs
We present a new scheme for computing shortest paths on real-weighted undirected graphs in the fundamental comparison-addition model. In an efficient preprocessing phase our algorithm creates a linear-size structure that facilitates single-source ...
Comments