Ryan Williams
ABSTRACT
We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two n × n matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense n-node directed graphs with arbitrary edge weights. On the real RAM, where additions and comparisons of reals are unit cost (but all other operations have typical logarithmic cost), the algorithm runs in time
[EQUATION]
and is correct with high probability. On the word RAM, the algorithm runs in [EQUATION] + n2+o(1) logM time for edge weights in ([0,M]∩Z)∪{∞}. Prior algorithms took either O(n3/logc n) time for various c ≤ 2, or O(Mαnβ) time for various α > 0 and β > 2.
The new algorithm applies a tool from circuit complexity, namely the Razborov-Smolensky polynomials for approximately representing AC0[p] circuits, to efficiently reduce a matrix product over the (min, +) algebra to a relatively small number of rectangular matrix products over F2, each of which are computable using a particularly efficient method due to Coppersmith. We also give a deterministic version of the algorithm running in n[EQUATION] time for some δ > 0, which utilizes the Yao-Beigel-Tarui translation of AC0[m] circuits into "nice" depth-two circuits.
Supplemental Material
- {AG94} Eric Allender and Vivek Gore. A uniform circuit lower bound for the permanent. SIAM J. Computing, 23(5):1026--1049, 1994. Google Scholar
Digital Library
- {AGM97} Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences, 54(2):255--262, 1997. Google ScholarDigital Library
- {AHU74} Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Series in Computer Science and Information Processing, 1974. Google ScholarDigital Library
- {Ajt83} Miklos Ajtai. Σ11 -formulae on finite structures. Annals of Pure and Applied Logic, 24:1--48, 1983.Google ScholarCross Ref
- {AYZ97} Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17:354--364, 1997.Google ScholarDigital Library
- {BCD+06} David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patraşcu, and Perouz Taslakian. Necklaces, convolutions, and X+Y. CoRR, abs/1212.4771, 2012. See also ESA'06.Google Scholar
- {BDH+12} Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, and Oded Schwartz. Communication-optimal parallel algorithm for Strassen's matrix multiplication. In Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and architectures, pages 193--204, 2012. Google ScholarDigital Library
- {BDLS12} Grey Ballard, Jim Demmel, Ben Lipshitz, and Oded Schwartz. Communication-avoiding parallel strassen: Implementation and performance. In Proceedings of 2012 International Conference for High Performance Computing, Networking, Storage and Analysis (SC), volume 12, 2012. Google ScholarDigital Library
- {BDP05} Ilya Baran, Erik D. Demaine, and Mihai Patraşcu. Subquadratic algorithms for 3SUM. Algorithmica, 50(4):584--596, 2008. See also WADS'05. Google ScholarDigital Library
- {BHP01} Gill Barequet and Sariel Har-Peled. Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard. Int. J. Comput. Geometry Appl., 11(4):465--474, 2001.Google ScholarCross Ref
- {BT94} Richard Beigel and Jun Tarui. On ACC. Computational Complexity, 4:350--366, 1994. Google ScholarDigital Library
- {BW09} Nikhil Bansal and Ryan Williams. Regularity lemmas and combinatorial algorithms. Theory of Computing, 8(4):69--94, 2012. See also FOCS'09.Google ScholarCross Ref
- {Cha06} Timothy M. Chan. All-pairs shortest paths for unweighted undirected graphs in o(mn) time. ACM Transactions on Algorithms, 8(4), 2012. See also SODA'06. Google ScholarDigital Library
- {Cha05} Timothy M. Chan. All-pairs shortest paths with real weights in O(n3/log n) time. Algorithmica, 50(2):236--243, 2008. See also WADS'05. Google ScholarDigital Library
- {Cha07} Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput., 39(5):2075--2089, 2010. See also STOC'07. Google ScholarDigital Library
- {CLPT02} Siddhartha Chatterjee, Alvin R. Lebeck, Praveen K. Patnala, and Mithuna Thottethodi. Recursive array layouts and fast matrix multiplication. IEEE Transactions on Parallel and Distributed Systems, 13(11):1105--1123, 2002. Google ScholarDigital Library
- {Cop82} Don Coppersmith. Rapid multiplication of rectangular matrices. SIAM J. Comput., 11(3):467--471, 1982.Google ScholarCross Ref
- {CSV84} Ashok K. Chandra, Larry Stockmeyer, and Uzi Vishkin. Constant depth reducibility. SIAM Journal on Computing, 13(2):423--439, 1984.Google ScholarCross Ref
- {DN09} Paolo D'Alberto and Alexandru Nicolau. Adaptive Winograd's matrix multiplications. ACM Transactions on Mathematical Software (TOMS), 36(1):3, 2009. Google ScholarDigital Library
- {Dob90} Wlodzimierz Dobosiewicz. A more efficient algorithm for the min-plus multiplication. International Journal of Computer Mathematics, 32(1-2):49--60, 1990.Google ScholarCross Ref
- {Flo62} Robert W. Floyd. Algorithm 97. Comm. ACM, 5-6:345, 1962.Google ScholarDigital Library
- {FM71} Michael J. Fischer and Albert R. Meyer. Boolean matrix multiplication and transitive closure. In IEEE Symposium on Switching and Automata Theory, pages 129--131, 1971. Google ScholarDigital Library
- {Fre75} Michael L. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. Comput., 5(1):49--60, 1976. See also FOCS'75.Google ScholarCross Ref
- {FSS81} Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13--27, April 1984. See also FOCS'81.Google ScholarCross Ref
- {FT87} Michael L. Fredman and Robert E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596--615, 1987. Google ScholarDigital Library
- {GG96} Brian Grayson and Robert Van De Geijn. A high performance parallel Strassen implementation. Parallel Processing Letters, 6(01):3--12, 1996.Google ScholarCross Ref
- {GO95} Anka Gajentaan and Mark H. Overmars. On a class of O(n2) problems in computational geometry. Comput. Geom., 5:165--185, 1995. Google ScholarDigital Library
- {GS13} Harold N. Gabow and Piotr Sankowski. Algebraic algorithms for b-matching, shortest undirected paths, and f-factors. In FOCS, pages 137--146, 2013. Google ScholarDigital Library
- {Han04} Yijie Han. Improved algorithm for all pairs shortest paths. Information Processing Letters, 91(5):245--250, 2004. Google ScholarDigital Library
- {Han06} Yijie Han. An O(n3(log log n/log n)5/4) time algorithm for all pairs shortest path. Algorithmica, 51(4):428--434, 2008. See also ESA'06. Google ScholarDigital Library
- {HMP+93} András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán. Threshold circuits of bounded depth. J. Comput. Syst. Sci., 46(2):129--154, 1993. Google ScholarDigital Library
- {HT12} Yijie Han and Tadao Takaoka. An O(n3 log log n/log2 n) time algorithm for all pairs shortest paths. In SWAT, volume 7357 of Springer LNCS, pages 131--141, 2012. Google ScholarDigital Library
- {Joh77} Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. J. ACM, 24(1):1--13, 1977. Google ScholarDigital Library
- {Ker70} Leslie R. Kerr. The effect of algebraic structure on the computation complexity of matrix multiplications. PhD thesis, Cornell University, Ithaca, NY, 1970.Google Scholar
- {MP80} William J. Masek and Michael S. Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20(1):18--31, 1980.Google ScholarCross Ref
- {MR95} Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Cambridge University Press, 1995.Google ScholarCross Ref
- {Mun71} Ian Munro. Efficient determination of the transitive closure of a directed graph. Information Processing Letters, 1:56--58, 1971. Google ScholarDigital Library
- {Pan81} Victor Ya. Pan. The bit-operation complexity of matrix multiplication and of all pair shortest path problem. Computers & Mathematics with Applications, 7(5):431--438, 1981.Google ScholarCross Ref
- {Pet04} Seth Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci., 312(1):47--74, 2004. Google ScholarDigital Library
- {PR05} Seth Pettie and Vijaya Ramachandran. A shortest path algorithm for real-weighted undirected graphs. SIAM Journal on Computing, 34(6):1398--1431, 2005. Google ScholarDigital Library
- {P10} Mihai Patraşcu. Towards polynomial lower bounds for dynamic problems. In STOC, pages 603--610, 2010. Google ScholarDigital Library
- {Raz87} Alexander A. Razborov. Lower bounds for the size of circuits of bounded depth over a complete basis with logical addition. Math. Notes Acad. Sci. USSR, 41(4):333--338, 1987. Translated from Mathematicheskie Zametki 41:4, 598--607, 1987.Google ScholarCross Ref
- {Rom80} F. Romani. Shortest-path problem is not harder than matrix multiplication. Information Processing Letters, 11:134--136, 1980.Google ScholarCross Ref
- {Sei95} Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci., 51(3):400--403, 1995. Google ScholarDigital Library
- {SEO03} Michael A. Soss, Jeff Erickson, and Mark H. Overmars. Preprocessing chains for fast dihedral rotations is hard or even impossible. Comput. Geom., 26(3):235--246, 2003. Google ScholarDigital Library
- {Smo87} Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In STOC, pages 77--82, 1987. Google ScholarDigital Library
- {Str69} Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13(4):354--356, 1969.Google ScholarDigital Library
- {SZ99} Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In FOCS, pages 605--615, 1999. Google ScholarDigital Library
- {Tak04} Tadao Takaoka. A faster algorithm for the all-pairs shortest path problem and its application. In Computing and Combinatorics, volume 3106 of Springer LNCS, pages 278--289. 2004.Google ScholarCross Ref
- {Tak05} Tadao Takaoka. An O(n3 log log n/log n) time algorithm for the all-pairs shortest path problem. Information Processing Letters, 96(5):155--161, 2005. Google ScholarDigital Library
- {Tak91} A new upper bound on the complexity of the all pairs shortest path problem. Information Processing Letters, 43(4):195--199, 1992. See also WG'91. Google ScholarDigital Library
- {Tak95} Tadao Takaoka. Subcubic cost algorithms for the all pairs shortest path problem. Algorithmica, 20(3):309--318, 1998. See also WG'95.Google ScholarCross Ref
- {VW10} Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In FOCS, pages 645--654, 2010. Google ScholarDigital Library
- {VW13} Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput., 42(3):831--854, 2013.Google ScholarCross Ref
- {War62} Stephen Warshall. A theorem on Boolean matrices. J. ACM, 9:11--12, 1962. Google ScholarDigital Library
- {Wil11} Ryan Williams. Non-uniform ACC circuit lower bounds. In IEEE Conference on Computational Complexity, pages 115--125, 2011. Google ScholarDigital Library
- {Wil13} Ryan Williams. Faster all-pairs shortest paths via circuit complexity. CoRR, abs/1312.6680, 2013. {Wil14} Ryan Williams. New algorithms and lower bounds for circuits with linear threshold gates. In STOC, page nearby, 2014. Google ScholarDigital Library
- {Yao90} Andrew Chi-Chih Yao. On ACC and threshold circuits. In FOCS, pages 619--627, 1990. Google ScholarDigital Library
- {Zwi02} Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289--317, 2002. Google ScholarDigital Library
- {Zwi04} Uri Zwick. A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths. In ISAAC 2004, volume 3341 of Springer LNCS, pages 921--932, 2004. Google ScholarDigital Library
Index Terms
- Faster all-pairs shortest paths via circuit complexity
Recommendations
Faster All-Pairs Shortest Paths via Circuit Complexity
We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two $n \times n$ matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense $n$-node directed graphs with ...
From Circuit Complexity to Faster All-Pairs Shortest Paths
We present a randomized method for computing the min-plus product (a.k.a. tropical product) of two $n \times n$ matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense $n$-node directed graphs with arbitrary ...
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
FOCS '13: Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer ScienceWe study dynamic (1+e)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of ~ O(...
Comments