We present a new randomized method for computing the min-plus product(a.k.a., tropical product) of two $n imes n$ matrices, yielding a fasteralgorithm for solving the all-pairs shortest path problem (APSP) in dense$n$-node directed graphs with arbitrary edge weights. On the real RAM, whereadditions and comparisons of reals are unit cost (but all other operations havetypical logarithmic cost), the algorithm runs in time[rac{n^3}{2^{Omega(log n)^{1/2}}}] and is correct with high probability.On the word RAM, the algorithm runs in $n^3/2^{Omega(log n)^{1/2}} +n^{2+o(1)}log M$ time for edge weights in $([0,M] cap {mathbbZ})cup{infty}$. Prior algorithms used either $n^3/(log^c n)$ time forvarious $c leq 2$, or $O(M^{lpha}n^{eta})$ time for various $lpha > 0$and $eta > 2$. The new algorithm applies a tool from circuit complexity, namely theRazborov-Smolensky polynomials for approximately representing ${sf AC}^0[p]$circuits, to efficiently reduce a matrix product over the $(min,+)$ algebra toa relatively small number of rectangular matrix products over ${mathbb F}_2$,each of which are computable using a particularly efficient method due toCoppersmith. We also give a deterministic version of the algorithm running in$n^3/2^{log^{delta} n}$ time for some $delta > 0$, which utilizes theYao-Beigel-Tarui translation of ${sf AC}^0[m]$ circuits into "nice" depth-twocircuits.
展开▼
机译：我们提出了一种新的随机方法，用于计算两个$ n times n $矩阵的最小加乘积（aka，热带乘积），从而产生了一个更快的算法，用于解决密集$ n $-中的所有对最短路径问题（APSP）具有任意边缘权重的节点定向图。在实数RAM上，实数的加法和比较是单位成本（但所有其他操作都具有典型的对数成本），该算法在时间 [ frac {n ^ 3} {2 ^ { Omega（ log n）^ { 1/2}}} ]且极有可能正确。在单词RAM上，算法以$ n ^ 3/2 ^ { Omega（ log n）^ {1/2}} + n ^ { 2 + o（1）} log M $时间以$（[0，M] cap { mathbbZ}） cup { infty } $计算边缘权重。先前的算法将$ n ^ 3 /（ log ^ cn）$时间用于各种$ c leq 2 $，或将$ O（M ^ { alpha} n ^ { beta}）$时间用于各种$ alpha> 0 $和$ beta> 2 $。新算法运用了电路复杂性的工具，即Razborov-Smolensky多项式，用于近似表示$ { sf AC} ^ 0 [p] $电路，以有效地减少$（ min，+）$代数toa的矩阵乘积。 $ { mathbb F} _2 $以上的矩形矩阵产品数量相对较少，由于Coppersmith的缘故，可以使用一种特别有效的方法来计算每一种。我们还给出了算法的确定性版本，该算法在$ n ^ 3/2 ^ { log ^ { delta} n} $时间内运行$ delta> 0 $的时间，它利用了$ {的Yao-Beigel-Tarui转换 sf AC} ^ 0 [m] $电路成“很好的”深度二电路。
展开▼
