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 x 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 n(3)/2(Omega(log n)1/2) and is correct with high probability. On the word RAM with wordsize log(n), the algorithm runs in n(3)/2(Omega(log n)1/2) + n(2+o(1)) log(nM) time for edge weights in ([0, M] boolean AND Z) boolean OR {infinity}. Prior algorithms took either O(n(3)/log(c)n) time for various c = 2, or O(M(alpha)n(beta)) time for various alpha 0 and beta 2. The new algorithm applies a tool from circuit complexity, namely the Razborov-Smolensky polynomials for approximately representing AC(0)[p] circuits, to efficiently reduce a matrix product over the (min, +) algebra to a relatively small number of rectangular matrix products over F-2, each of which is computable using a particularly efficient method due to Coppersmith. We also give a deterministic version of the algorithm running in n(3)/2log(delta)n time for some delta 0, which utilizes the Yao-Beigel-Taru translation of AC(0)[m] circuits into "nice" depth-two circuits.