Faster all-pairs shortest paths via circuit complexity

Introduction

Since the 1970s [Mun71, FM71, AHU74] it has been known that the search for faster algorithms for APSP is equivalent to the search for faster algorithms for the min-plus (or max-plus) matrix product (a.k.a. distance product or tropical matrix multiplication), defined as:

That is, $\min$ plays the role of addition, and $+$ plays the role of multiplication. A $T(n)$-time algorithm exists for this product if and only if there is an $O(T(n))$-time algorithm for APSP.Technically speaking, to reconstruct the shortest paths, we also need to compute the product $(A\odot B)[i,j]=\operatorname*{arg\,min}_{k}(A[i,k]+B[k,j])$, which returns (for all $i,j$) some $k$ witnessing the minimum $A[i,k]+B[k,j]$. However, all known distance product algorithms (including ours) have this property.

Perhaps inspired by the surprising $n^{2.82}$ matrix multiplication algorithm of Strassen [Str69] over rings,As $\min$ and $\max$ do not have additive inverses, min-plus algebra and max-plus algebra are not rings, so fast matrix multiplication algorithms do not directly apply to them. Fredman [Fre75] initiated the development of $o(n^{3})$ time algorithms for APSP. He discovered a non-uniform decision tree computing the $n\times n$ min-plus product with depth $O(n^{2.5})$ (but with size $2^{\Theta(n^{2.5})}$). Combining the decision tree with a lookup table technique, he obtained a uniform APSP algorithm running in about $n^{3}/\log^{1/3}n$ time. Since 1975, many subsequent improvements on Fredman’s algorithm have been reported (see Table 1).There have also been parallel developments in APSP algorithms on sparse graphs [Joh77, FT87, PR05, Pet04, Cha06] and graphs with small integer weights [Rom80, Pan81, Sei95, Tak95, AGM97, SZ99, Zwi02, GS13]. The small-weight algorithms are pseudopolynomial, running in time $O(M^{\alpha}n^{\beta})$ for various $\alpha>0$ and various $\beta$ greater than the (ring) matrix multiplication exponent. However, all these improvements have only saved $\log^{c}n$ factors over Floyd-Warshall: most recently, Chan [Cha07] and Han and Takaoka [HT12] give time bounds of roughly $n^{3}/\log^{2}n$.

The consensus appears to be that the known approaches to general APSP may never save more than small ${\text{poly}}(\log n)$ factors in the running time. The methods (including Fredman’s) use substantial preprocessing, lookup tables, and (sometimes) bit tricks, offloading progressively more complex operations into tables such that these operations can then be executed in constant time, speeding up the algorithm. It is open whether such techniques could even lead to an $n^{3}/\log^{3}n$ time Boolean matrix multiplication (with logical OR as addition), a special case of max-plus product. V. Vassilevska Williams and the author [VW10] proved that a large collection of fundamental graph and matrix problems are subcubic equivalent to APSP: Either all these problems are solvable in $n^{3-{\varepsilon}}$ time for some ${\varepsilon}>0$ (a.k.a. “truly subcubic time”), or none of them are. This theory of APSP-hardness has nurtured some pessimism that truly subcubic APSP is possible.

We counter these doubts with a new algorithm for APSP running faster than $n^{3}/\log^{k}n$ time, for every $k$.

A similar $n^{2+o(1)}\log M$ time factor would necessarily appear in a complete running time description of all previous algorithms when implemented on a machine that takes bit complexity into account, such as the word RAM—note the input itself requires $\Omega(n^{2}\log M)$ bits to describe in the worst case. In the real RAM model, where additions and comparisons of real numbers given in the input are unit cost, but all other operations have typical cost, the algorithm runs in the “strongly polynomial” bound of $n^{3}/2^{\Omega(\log n)^{1/2}}$ time. Most prior algorithms for the general case of APSP also have implementations in the real RAM. (For an extended discussion, see Section 2 of Zwick [Zwi04].)

The new algorithm avoids an exponential blowup by exploiting the fact that $\min$ and addition are simple operations from the point of view of Boolean circuit complexity. Namely, these operations are both in ${\sf AC}^{0}$, i.e., they have circuits of constant-depth and polynomial-size over AND/OR/NOT gates of unbounded fan-in. It follows that min-plus inner products can be computed in ${\sf AC}^{0}$, and the new algorithm manipulates such circuits at the bit-level. (This also means the approach is highly non-black-box, and not subject to lower bounds based on additions and comparisons alone; this is necessary, due to Kerr’s $\Omega(n^{3})$ lower bound.) ${\sf AC}^{0}$ operations are very structured and have many known limitations (starting with [Ajt83, FSS81]). Circuit lower bound techniques often translate algorithmically into nice methods for manipulating circuits.

Minimum weight triangle: Given an $n$-node graph with real edge weights, compute $u,v,w$ such that $(u,v),(v,w),(w,u)$ are edges and the sum of edge weights is minimized.

Minimum cycle: Given an $n$-node graph with real positive edge weights, find a cycle of minimum total edge weight.

Second shortest paths: Given an $n$-node directed graph with real positive edge weights and two nodes $s$ and $t$, determine the second shortest simple path from $s$ to $t$.

Replacement paths: Given an $n$-node directed graph with real positive edge weights and a shortest path $P$ from node $s$ to node $t$, determine for each edge $e\in P$ the shortest path from $s$ to $t$ in the graph with $e$ removed.

Faster algorithms for some sparse graph problems also follow from Theorem 1.1. An example is that of finding a minimum weight triangle in a sparse graph:

In other words, this is the usual discrete convolution of two vectors in $(\min,+)$ algebra.

Is it possible that the approach of this paper can be extended to give a “truly subcubic” APSP algorithm, running in $n^{3-{\varepsilon}}$ time for some ${\varepsilon}>0$? If so, we might require an even more efficient way of representing min-plus inner products as inner products over the integers. Very recently, the author discovered a way to efficiently evaluate large depth-two linear threshold circuits [Wil13] on many inputs. The method is general enough that, if min-plus inner product can be efficiently implemented with depth-two threshold circuits, then truly subcubic APSP follows. For instance:

To phrase it another way, the hypothesis that APSP is not in truly subcubic time implies interesting circuit lower bounds.

In Section 2, we try to provide a relatively succinct exposition of how to solve APSP in less than $n^{3}/\log^{k}n$ time for all $k$, in the case where the edge weights are not too large (e.g., at most ${\text{poly}}(n)$). In Section 3 we prove Theorem 1.1 in full, by expanding considerably on the arguments in Section 2. In Section 4 we illustrate one of the many applications, and consider the possibility of extending our approach to a truly subcubic algorithm for APSP. We conclude in Section 5.

A relatively short argument for faster APSP

We begin with a succinct exposition of a good algorithm for all-pairs shortest paths, at least in the case of reasonable-sized weights. This will illustrate most of the main ideas in the full algorithm.

There is a deterministic algorithm for APSP which, for some $\delta>0$, runs in time

To simplify the presentation, we will not be explicit in our choice of $\delta$ here; that lovely torture will be postponed to the next section. Another mildly undesirable property of Theorem 2.1 is that the bound is only meaningful for $M\leq 2^{2^{{\varepsilon}(\log n)^{\delta}}}$ for sufficiently small ${\varepsilon}>0$. So this is not the most general bound one could hope for, but it is effective when the edge weights are in the range $\{0,1,\ldots,{\text{poly}}(n)\}$, which is already a difficult case for present algorithms. The $(\log M)^{1+o(1)}$ factor will be eliminated in the next section.

A min-plus matrix multiplication simply represents a collection of all-pairs min-plus inner products over a set of vectors.

Given $u,v\in{\cal W}^{d}$ encoded as $O(d\log M)$-bit strings, $(u\star v)$ is computable with constant-depth AND/OR/NOT circuits of size $(d\log M)^{O(1)}$. That is, the min-plus inner product function is computable in ${\sf AC}^{0}$ for every $d$ and $M$.

The proof is relatively straightforward; it is given in Appendix A for completeness. Next, we show that a small ${\sf AC}^{0}$ circuit can be quickly evaluated on all pairs of inputs of one’s choice. The first step is to deterministically reduce ${\sf AC}^{0}$ circuits to depth-two circuits with a symmetric function (a multivariate Boolean function whose value only depends on the sum of the variables) computing the output gate and AND gates of inputs (or their negations) on the second layer. Such circuits are typically called ${\sf SYM}^{+}$ circuits [BT94]. It is known that constant-depth circuits with AND, OR, NOT, and MOD$m$ gates of size $s$ (a.k.a. ${\sf ACC}$ circuits) can be efficiently translated into ${\sf SYM}^{+}$ circuits of size $2^{(\log s)^{c}}$ for some constant $c$ depending on the depth of the circuit and the modulus $m$:A MOD$m$ gate outputs $1$ if and only if the sum of its input bits is divisible by $m$.

Moreover, given the number of ANDs in the circuit evaluating to $1$, the symmetric function itself can be evaluated in $(\log s)^{O(f(e,m))}$ time.

The second step is to quickly evaluate these polynomials on many chosen inputs, using rectangular matrix multiplication. Specifically, we require the following:

For all sufficiently large $N$, multiplication of an $N\times N^{.172}$ matrix with an $N^{.172}\times N$ matrix can be done in $O(N^{2}\log^{2}N)$ arithmetic operations.See Appendix C for a detailed exposition of this algorithm.

Let $p$ be a $2k$-variate polynomial over the integers (in its monomial representation) with $m\leq n^{0.1}$ monomials, along with $A,B\subseteq\{0,1\}^{k}$ such that $|A|=|B|=n$. The polynomial $p(a_{1},\ldots,a_{k},b_{1},\ldots,b_{k})$ can be evaluated over all points $(a_{1},\ldots,a_{k},b_{1},\ldots,b_{k})\in A\times B$ in $n^{2}\cdot{\text{poly}}(\log n)$ arithmetic operations.

Note that the obvious polynomial evaluation algorithm would require $n^{2.1}$ arithmetic operations.

Putting the pieces together, we obtain our “warm-up” APSP algorithm:

But $K\leq n^{0.1}$ precisely when $(\log(d\log M))^{c}\leq 0.1\log n$, i.e.,

Proof of The Main Theorem

First, we can assume without loss of generality that for all $i,j$, there is a unique $k$ achieving the minimum $A[i,k]+B[k,j]$. One way to enforce this is to change all initial $A[i,j]$ entries at the beginning to $A[i,j]\cdot(n+1)+j$, and all $B[i,j]$ entries to $B[i,j]\cdot(n+1)$, prior to sorting. These changes can be made with only $O(\log n)$ additions per entry; e.g., by adding $A[i,j]$ to itself for $O(\log n)$ times. Then, $\min_{k}A[i,k]+B[k,j]$ becomes

where $k^{\star}$ is the minimum integer achieving $\min_{k}A[i,k]+B[k,j]$.

Next, we encode a trick of Fredman [Fre75] in the computation; his trick is simply that

This subtle trick has been applied in most prior work on faster APSP. It allows us to “prepare” $A$ and $B$ by taking many differences of entries, before making explicit comparisons between entries. Namely, we construct matrices $A^{\prime}$ and $B^{\prime}$ which are $n\times d^{2}$ and $d^{2}\times n$. The columns of $A^{\prime}$ and rows of $B^{\prime}$ are indexed by pairs $(k,k^{\prime})$ from $[d]^{2}$. We define:

Observe that $A^{\prime}[i,(k,k^{\prime})]\leq B^{\prime}[(k,k^{\prime}),j]$ if and only if $A[i,k]+B[k,j]\leq A[i,k^{\prime}]+B[k^{\prime},j]$.

For each column $(k,k^{\prime})$ of $A^{\prime}$ and corresponding row $(k,k^{\prime})$ of $B^{\prime}$, sort the $2n$ numbers in the set

and replace each $A^{\prime}[i,(k,k^{\prime})]$ and $B[(k,k^{\prime}),j]$ by their rank in the sorted order on $S_{(k,k^{\prime})}$, breaking ties arbitrarily (giving $A$ entries precedence over $B$ entries). Call these new matrices $A^{\prime\prime}$ and $B^{\prime\prime}$. The key properties of this replacement are:

All entries of $A^{\prime\prime}$ and $B^{\prime\prime}$ are from the set $\{1,\ldots,2n\}$.

$A^{\prime\prime}[i,(k,k^{\prime})]\leq B^{\prime\prime}[(k,k^{\prime}),j]$ if and only if $A^{\prime}[i,(k,k^{\prime})]\leq B^{\prime}[(k,k^{\prime}),j]$. That is, the outcomes of all comparisons have been preserved.

For every $i,j$, there is a unique $k$ such that $A^{\prime\prime}[i,(k,k^{\prime})]\leq B^{\prime\prime}[(k,k^{\prime}),j]$ for all $k^{\prime}$; this follows from the fact that there is a unique $k$ achieving the minimum $A[i,k]+B[k,j]$.

Here we are using the notation that, for a logical expression $Q$, the expression [$Q$] is either or $1$, and it is $1$ if and only if $Q$ is true.

In the expression $P$, there are $d$ different ANDs over $d$ comparisons. In order to get a “short” polynomial, we need to reduce the fan-in of the ANDs. Razborov and Smolensky proposed the following construction: for an AND over $d$ variables $y_{1},\ldots,y_{d}$, let $e\geq 1$ be an integer, choose independently and uniformly at random $e\cdot d$ bits $r_{1,1},\ldots,r_{1,d},r_{2,1},\ldots,r_{2,d},~{}\ldots~{},r_{e,1},\ldots,r_{e,d}\in\{0,1\}$, and consider the expression

where $+$ corresponds to addition modulo $2$. Note that when the $r_{i,j}$ are fixed constants, $E$ is an AND of $e$ XORs of at most $d+1$ variables $y_{j}$ along with possibly the constant $1$.

For every fixed $(y_{1},...,y_{d})\in\{0,1\}^{d}$,

For completeness, we give the simple proof. For a given point $(y_{1},\ldots,y_{d})$, first consider the expression $F_{i}=1+\oplus_{j=1}^{d}r_{i,j}\cdot(y_{j}+1)$. If $y_{1}\wedge\cdots\wedge y_{d}=1$, then $(y_{j}+1)$ is modulo $2$ for all $j$, and hence $F_{i}=1$ with probability $1$. If $y_{1}\wedge\cdots\wedge y_{d}=0$, then there is a subset $S$ of $y_{j}$’s which are , and hence a subset $S$ of $(y_{j}+1)$’s that are $1$. The probability we choose $r_{i,j}=1$ for an odd number of the $y_{j}$’s in $S$ is at exactly $1/2$. Hence the probability that $F_{i}=0$ in this case is exactly $1/2$.

Since $E(y_{1},\ldots,y_{d})=\wedge_{i=1}^{e}F_{i}$, it follows that if $y_{1}\wedge\cdots\wedge y_{d}=1$, then $E=1$ with probability $1$. Since the $r_{i,j}$ are independent, if $y_{1}\wedge\cdots\wedge y_{d}=0$, then the probability is only $1/2^{e}$ that for all $i$ we have $r_{i,j}=1$ for an odd number of $y_{j}=0$. Hence the probability is $1-1/2^{e}$ that some $F_{i}(y_{1},\ldots,y_{d})=0$, completing the proof.

Now set $e=2+\log d$, so that $E$ fails on a point $y$ with probability at most $1/(4d)$. Suppose we replace each of the $d$ ANDs in expression $P$ by the expression $E$, yielding:

By the union bound, the probability that the (randomly generated) expression $P^{\prime}$ differs from $P$ on a given row $A^{\prime\prime}[i,:]$ and column $B^{\prime\prime}[:,j]$ is at most $1/4$.

Next, we open up the $d^{2}$ comparisons in $P$ and simulate them with low-depth circuits. Think of the entries of $A^{\prime\prime}[i,(k,k^{\prime})]$ and $B^{\prime\prime}[(k,k^{\prime}),j]$ as bit strings, each of length $t=1+\log n$. To check whether $a\leq b$ for two $t$-bit strings $a=a_{1},...,a_{t}$ and $b=b_{1},...,b_{t}$ construed as positive integers in $\{1,\ldots,2^{t}\}$, we can compute (from Lemma 2.1)

where $+$ again stands for addition modulo $2$. (We can replace the outer $\vee$ with a $\oplus$, because at most one of the $t$ expressions inside of the $\oplus$ can be true for any $a$ and $b$.)

The $LEQ$ circuit is an XOR of $t+1$ ANDs of fan-in $\leq t$ of XORs of fan-in at most 3. Applying Claim 1, we replace the ANDs with a randomly chosen expression $E^{\prime}(e_{1},\ldots,e_{t})$, which is an AND of fan-in $e^{\prime}$ (for some parameter $e^{\prime}$ to be determined) of XORs of $\leq t$ fan-in. The new expression $LEQ^{\prime}$ now has the form

that is, we have an XOR of $t+1$ fan-in, of ANDs of fan-in $e^{\prime}$, of XORs of $\leq t$ fan-in, of XORs of fan-in at most 3.

In fact, an anonymous STOC referee pointed out that, by performing additional preprocessing on the matrices $A^{\prime\prime}$ and $B^{\prime\prime}$, we can reduce the $LEQ^{\prime}$ expression further, to have the form

Recall in the expression $P^{\prime}$, there are $d^{2}$ comparisons, and hence $d^{2}$ copies of the $LEQ$ circuit are needed. Setting

we ensure that, for a given row $i$, column $j$, and $t$ for $P^{\prime}$, $d^{2}$ copies of the $LEQ^{\prime}$ circuit give the same output as $LEQ$ with probability at least $3/4$.

Further simplifying, this quantity is at most

Let $m^{\prime\prime}$ denote the quantity in (2). Provided $m^{\prime\prime}\leq n^{0.1}$, we will be able to apply a rectangular matrix multiplication in the final step. This is equivalent to

Recall $t=1+\log n$, and note that $\log_{2}(m^{\prime\prime})$ expands to a sum of various powers of logs. For $d\geq t$, the dominant term in $\log_{2}(m^{\prime\prime})$ is $2(\log^{2}d)(\log 3)\leq O((\log d)^{2})$. Choosing

for sufficiently small $\delta>0$, inequality (3) will be satisfied, and the number $m^{\prime\prime}$ will be less than $n^{0.1}$.

Recall that if we have independent random variables $Y_{i}$ that are -$1$ valued with $0<E[Y_{i}]<1$, the random variable $Y:=\sum_{i=1}^{k}Y_{i}$ satisfies the tail bound

(e.g., in Motwani and Raghavan [MR95], this is Theorem 4.2). Applying this bound,

Therefore for $d=2^{\delta(\log n)^{1/2}}$, the algorithm outputs the min-plus product of an $n\times d$ and $d\times n$ matrix in $n^{2}\cdot{\text{poly}}(\log n)+n\cdot d^{2}\cdot(\log M)$ time, with probability at least $1-(\log n)/n^{2}$.

Applying this algorithm to $n/d$ different $n\times d$ and $d\times n$ min-plus products, the min-plus product of two $n\times n$ matrices is computable in time $n^{3}/2^{\Omega(\log n)^{1/2}}$ on the real RAM with probability at least $1-(\log n)/n$, by the union bound. (On the word RAM, there is an extra additive factor of $n^{2+o(1)}\cdot\log M$, for the initial application of Fredman’s trick.)

The APSP algorithm can be made deterministic with some loss in the running time, but still asymptotically better than $n^{3}/(\log n)^{k}$ for every $k$. See Appendix B for the proof.

There is a $\delta>0$ and a deterministic algorithm for APSP running in $n^{3}/2^{(\log n)^{\delta}}$ time on the real RAM.

Some Applications

All applications referred to the introduction follow straightforwardly from the literature, except for possibly:

We follow the high-degree/low-degree trick of Alon, Yuster, Zwick [AYZ97]. To find a minimum edge-weight triangle with $m$ edges, let $\Delta\in[1,m]$ be a parameter and consider two possible scenarios:

The min-weight triangle contains a node of degree at most $\Delta$. Here, $O(m\cdot\Delta)$ time suffices to search for the triangle: try all possible edges $\{u,v\}$ with $\deg(v)\leq\Delta$, and check if there is a neighbor of $v$ which forms a triangle with $u$, recording the triangle encountered of smallest weight.

To minimize the overall running time, we want

It seems likely that the basic approach taken in this paper can be extended to discover even faster APSP algorithms. Here we outline one concrete direction to pursue.

It is an open frontier in circuit complexity to exhibit explicit functions which are not computable efficiently with ${\sf SYM}\circ{\sf THR}$ circuits. As far as we know, it could be that huge complexity classes like ${\sf EXP}^{\sf NP}$ have ${\sf SYM}\circ{\sf THR}$ circuits with only ${\text{poly}}(n)$ gates. (Allowing exponential weights is crucial: there are lower bounds for depth-two threshold circuits with small weights [HMP+93].)

That is, efficient depth-two circuits for $(\min,+)$ inner product would imply a truly subcubic time algorithm for APSP. The proof applies a recent algorithm of the author:

Given a ${\sf SYM}\circ{\sf THR}$ circuit $C$ with $2k$ inputs and at most $n^{1/12}$ gates with threshold weights of absolute value at most $W_{b}$, and given two sets $A,B\subseteq\{0,1\}^{k}$ where $|A|=|B|=n$, we can evaluate $C$ on all $n^{2}$ points in $A\times B$ using $n^{2}\cdot{\text{poly}}(\log n)+n^{1+1/12}\cdot{\text{poly}}(\log n,\log W_{b})$ time.

A similar theorem also holds for depth-two threshold circuits (${\sf THR}\circ{\sf THR}$). Note the obvious algorithm for the above evaluation problem would take at least $\Omega(n^{2+1/12})$ time.

To compute the $(\min,+)$-multiplication of two $n\times n$ matrices, we reduce it into $n/d$ multiplies of $n\times d$ and $d\times n$ (as in Theorems 2.1 and 1.1), resulting in an algorithm running in time $O(n^{3-1/(12k)}\cdot(\log M)^{k})$.

Discussion

1. Subquadratic 3SUM. Along with APSP, the 3SUM problem is another notorious polynomial-time solvable problem: given a list of integers, are there three which sum to zero? For lists of $n$ numbers, an $O(n^{2})$ time algorithm is well-known, and the conjecture that no $n^{1.999}$ time algorithm exists is significant in computational geometry and data structures, with many intriguing consequences [GO95, BHP01, SEO03, Pat10, VW13]. Baran, Demaine, and Patrascu [BDP05] showed that 3SUM is in about $n^{2}/\log^{2}n$ time (omitting ${\text{poly}}(\log\log n)$ factors). Can this be extended to $n^{2}/2^{(\log n)^{\delta}}$ time for some $\delta>0$? It is natural to start with solving Convolution-3SUM, defined by Patrascu [Pat10] as: given an array $A$ of $n$ integers, are there $i$ and $j$ such that $A[i]+A[j]=A[i+j\pmod{n}]$? Although this problem looks superficially easier than 3SUM, Patrascu showed that if Convolution-3SUM is in $n^{2}/(f(n\cdot f(n)))^{2}$ time then 3SUM is in $n^{2}/f(n)$ time. That is, minor improvements for Convolution-3SUM would yield similar improvements for 3SUM.

2. Subquadratic String Matching. There are many problems involving string matching and alignment which are solvable using dynamic programming in $O(n^{2}/\log n)$ time, on strings of length $n$. A prominent example is computing the edit distance [MP80]. Can edit distance be computed in $n^{2}/2^{(\log n)^{\delta}}$ time?

3. Practicality? There are two potential impediments to making the approach of this paper work in practice: (1) the translation from ${\sf AC}^{0}$ circuits to polynomials, and (2) Coppersmith’s matrix multiplication algorithm. For case (1), there are no large hidden constants inherent in the Razborov-Smolensky translation, however the expansion of the polynomial as an XOR of ANDs yields a quasi-polynomial blowup. A careful study of alternative translations into polynomials would likely improve this step for practice. For case (2), Coppersmith’s algorithm as described in Appendix C consists of a series of multiplications with Vandermonde and inverse Vandermonde matrices (which are very efficient), along with a recursive step on $2\times 3$ and $3\times 2$ matrices, analogous to Strassen’s famous algorithm. We see no theoretical reason why this algorithm (implemented properly) would perform poorly in practice, given that Strassen’s algorithm can be tuned for practical gains [GG96, CLPT02, DN09, BDLS12, BDH+12]. Nevertheless, it would likely be a substantial engineering challenge to turn the algorithms of this paper into high-performance software.

5. Truly Subcubic APSP? What other circuit classes can compute $(\min,+)$ inner product and also permit a fast evaluation algorithm on many inputs? This question now appears to be central to the pursuit of truly subcubic ($n^{3-{\varepsilon}}$ time) APSP. Although we observe in the paper that $(\min,+)$ inner product is efficiently computable in ${\sf AC}^{0}$, the usual algebraic $(+,\times)$ inner product is in fact not in ${\sf AC}^{0}$. (Multiplication is not in ${\sf AC}^{0}$, by a reduction from Parity [CSV84].) This raises the intriguing possibility that $(\min,+)$ matrix product (and hence APSP) is not only in truly subcubic time, but could be easier than integer matrix multiplication. A prerequisite to this possibility would be to find new Boolean matrix multiplication algorithms which do not follow the Strassenesque approaches of the last 40+ years. Only minor progress on such algorithms has been recently made [BW09].

Many thanks to Virginia Vassilevska Williams; without her as a sounding board, I would have stopped thinking about APSP a long time ago. I’m also grateful to Uri Zwick, Farah Charab, and the STOC referees for helpful comments. Thanks also to Eric Allender for a discussion on references.

References

Appendix A Proof of Lemma 2.1

Before giving the circuit, let us briefly discuss the encoding of $\infty$. In principle, all we need is that $\infty$ encodes an integer greater than $2M$, and that addition of $\infty$ with any number equals $\infty$ again. With that in mind, we use the following convention: $t=3+\log M$ bits are allocated to encode each number in $\{0,\ldots,M\}$ (with two leading zeroes), and $\infty$ is defined as the all-ones string of $t$ bits.

The addition of two $t$-bit strings $x$ and $y$ is computable in $t^{O(1)}$ size and constant depth, using a “carry-lookahead” adder [SV84] (with an improved size bound in [CFL85]). Recall that a carry-lookahead adder determines in advance:

which bits of $x$ and $y$ will “generate” a $1$ when added, by taking the AND of each matching pair of bits from $x$ and $y$, and

which bits of $x$ and $y$ will “propagate” a $1$ if given a $1$ from the summation of lower bits, by taking the XOR of each matching pair of bits.

The “generate” and “propagate” bits can be generated in constant depth. Given them, in parallel we can determine (for all $i$) which bits $i$ of the addition will generate a carry in constant depth, and hence determine the sum in constant depth. (To handle the case of $\infty$, we simply add a side circuit which computes in parallel if one of the inputs is all-$1$s, in which case all output bits are forced to be $1$.)

Chandra, Stockmeyer, and Vishkin [CSV84] show how to compute the minimum of a collection of numbers (given as bit strings) in ${\sf AC}^{0}$. For completeness, we give a construction here. First, the comparison of two $t$-bit strings $x$ and $y$ (construed as non-negative integers) is computable in ${\sf AC}^{0}$. Define

where $+$ stands for addition modulo $2$. The first disjunct is true if and only if $x=y$. For the second disjunct and given $i=1,\ldots,t$, the inner expression is true if and only if the first $i-1$ bits of $x$ and $y$ are equal, the $i$th bit of $x$ is , and the $i$th bit of $y$ is 1. Replacing each $1+a+b$ with $(\neg a\vee b)\wedge(a\vee\neg b)$, we obtain an ${\sf AC}^{0}$ circuit.

Appendix B Appendix: Derandomizing the APSP algorithm

Reminder of Theorem 3.1 There is a $\delta>0$ and a deterministic algorithm for APSP running in $n^{3}/2^{(\log n)^{\delta}}$ time on the real RAM.

The proof combines the use of Fredman’s trick in Theorem 1.1 with the deterministic reduction from circuits to polynomials in Theorem 2.1.

Therefore we can reduce an $n\times d$ and $d\times n$ min-plus matrix product to a matrix product over the integers, by replacing each row $u$ of the first matrix by a corresponding $u^{\prime}$ of length

We derive an upper bound on $d$ as follows:

hence $d=2^{(0.1\log n)^{1/c}/4}$ suffices for sufficiently large $n$.

Examining the proof of Theorem 2.2 shows that we can estimate $c=2^{\Theta(d^{\prime})}$, where $d^{\prime}$ is the depth of the original ${\sf AC}^{0}$ circuit. However, as Beigel and Tarui’s proof also works for the much more expressive class ${\sf ACC}$ (and not just ${\sf AC}^{0}$), we are confident that better estimates on $c$ are possible with a different argument, and hence refrain from calculating an explicit bound here.

Appendix C Appendix: An exposition of Coppersmith’s algorithm

In 1982, Don Coppersmith proved that the rank (that is, the number of essential multiplications) of $N\times N^{0.1}$ and $N^{0.1}\times N$ matrix multiplication is at most $O(N\log^{2}N)$. Prior work has observed that his algorithm can also be used to show that the total number of arithmetic operations for the same matrix multiply is $N\cdot{\text{poly}}(\log N)$. However, the implication is not immediate, and uses specific properties of Coppersmith’s algorithm. Because this result is so essential to this work and another recent circuit lower bound [Wil13], we give a self-contained exposition here.

For all sufficiently large $N$, the rank of $N\times N^{.1}\times\times N$ matrix multiplication is at most $O(N^{2}\log^{2}N)$.

We wish to derive the following consequence of Coppersmith’s construction, which has been mentioned in the literature before [SM83, ACPS09, Wil11]:

For all sufficiently large $N$, and $\alpha\leq.172$, multiplication of an $N\times N^{\alpha}$ matrix with an $N^{\alpha}\times N$ matrix can be done in $N^{2}\cdot{\text{poly}}(\log N)$ arithmetic operations, over any field with $O(2^{{\text{poly}}(\log N)})$ elements.

Note Lemma C.1 has been “improved” in the sense that the upper bound on $\alpha$ has been increased mildly over the years [Cop97, HP98, KZHP08, Gal12]. However, these later developments only run in $N^{2+o(1)}$ time, not $N^{2}\cdot{\text{poly}}(\log N)$ time (which we require). Our exposition will expand on the informal description given in recent work [Wil11].

First, observe that the implication from Theorem C.1 to Lemma C.1 is not immediate. For example, it could be that Coppersmith’s algorithm is non-uniform, making it difficult to apply. As far as we know, one cannot simply take “constant size” arithmetic circuits implementing the algorithm of Theorem C.1 and recursively apply them. In that case, the ${\text{poly}}(\log N)$ factor in the running time would then become $N^{{\varepsilon}}$ for some constant ${\varepsilon}>0$ (depending on the size of the constant-size circuit). To keep the overhead polylogarithmic, we have to unpack the algorithm and analyze it directly.

Coppersmith’s algorithm builds on many other tools from prior matrix multiplication algorithms, many of which can be found in the highly readable book of Pan [Pan84]. Here we will give a very brief tutorial of some of the aspects.

Essentially all methods for matrix multiplication are bilinear (and if not, they can be converted into such algorithms), meaning that they can be expressed in the so-called trilinear form

where $\alpha_{ij}$, $\beta_{ij}$, and $\gamma_{ij}$ are constant-degree polynomials in $x$ over the field, and $p(x)$ is a polynomial with constant coefficient . Such an algorithm can be converted into one with no polynomials and minimal extra overhead (as described in Coppersmith’s paper). Typically one thinks of $A_{ik}$ and $B_{kj}$ as entries in the input matrices, and $C_{ji}$ as indeterminates, so the LHS of (4) corresponds to a polynomial whose $C_{ji}$ coefficient is the $ij$ entry of the matrix product. Note the transpose of the third matrix $C$ corresponds to the final matrix product.

To give an explicit example, we assume the reader is familiar with Strassen’s famous method for $2\times 2\times 2$ matrix multiply. Strassen’s algorithm can be expressed in the form of (4) as follows:

The LHS of (4) and (C.1) represents the trace of the product of three matrices $A$, $B$, and $C$ (where the $ij$ entry of matrix $X$ is $X_{ij}$). It is well known that every bilinear algorithm naturally expresses multiple algorithms through this trace representation. Since

if we think of $A$ as a symbolic matrix and consider (4), we obtain a new algorithm for computing a matrix $A$ when given $B$ and $C$. Similarly, we get an algorithm for computing a $B$ when given $A$ and $C$, and analogous statements hold for computing $A^{T}$, $B^{T}$, and $C^{T}$. So the aforementioned algorithm for multiplying a sparse $2\times 3$ and sparse $3\times 2$ yields several other algorithms.

Schönhage’s decomposition paradigm.

Coppersmith’s algorithm follows a specific paradigm introduced by Schönhage [Sch81] which reduces arbitrary matrix products to slightly larger matrix products with “structured nonzeroes.” The general paradigm has the following form. Suppose we wish to multiply two matrices $A^{\prime\prime}$ and $B^{\prime\prime}$.

First we preprocess $A^{\prime\prime}$ and $B^{\prime\prime}$ in some efficient way, decomposing $A^{\prime\prime}$ and $B^{\prime\prime}$ into structured matrices $A,A^{\prime},B,B^{\prime}$ so that $A^{\prime\prime}\cdot B^{\prime\prime}=A^{\prime}\cdot A\cdot B\cdot B^{\prime}$. (Note, the dimensions of $A^{\prime}\cdot A$ may differ from $A^{\prime\prime}$, and similarly for $B^{\prime}\cdot B$ and $B^{\prime\prime}$.) The matrices $A$ and $B$ are sparse “partial” matrices directly based on $A^{\prime\prime}$ and $B^{\prime\prime}$, but they have larger dimensions, and only contain nonzeroes in certain structured parts. The matrices $A^{\prime}$ and $B^{\prime}$ are very simple and explicit matrices of scalar constants, chosen independently of $A^{\prime\prime}$ and $B^{\prime\prime}$. (In particular, $A^{\prime}$ and $B^{\prime}$ are Vandermonde-style matrices.)

Next, we apply a specialized constant-sized matrix multiplication algorithm in a recursive manner, to multiply the structured $A$ and $B$ essentially optimally. Recall that Strassen’s famous matrix multiplication algorithm has an analogous form: it starts with a seven-multiplication product for $2\times 2\times 2$ matrix multiplication, and recursively applies this to obtain a general algorithm for $2^{M}\times 2^{M}\times 2^{M}$ matrix multiplication. Here, we will use an optimal algorithm for multiplying constant-sized matrices with zeroes in some of the entries; when this algorithm is recursively applied, it can multiply sparse $A$ and $B$ with nonzeroes in certain structured locations.

Finally, we postprocess the resulting product $C$ to obtain our desired product $A^{\prime\prime}\cdot B^{\prime\prime}$, by computing $A^{\prime}\cdot C\cdot B^{\prime}$. Using the simple structure of $A^{\prime}$ and $B^{\prime}$, the matrix products $D:=A^{\prime}\cdot C$ and $D\cdot B^{\prime}$ can be performed very efficiently. Our aim is to verify that each step of this process can be efficiently computed, for Coppersmith’s full matrix multiplication algorithm.

C.2 The algorithm

The construction of Coppersmith begins by taking input matrices $A^{\prime\prime}$ of dimensions $2^{4M/5}\times{M\choose 4M/5}2^{4M/5}$ and $B^{\prime\prime}$ of dimensions ${M\choose 4M/5}2^{4M/5}\times 2^{M/5}$ where $M\approx\log N$, and obtains an $O(5^{M}{\text{poly}}(M))$ algorithm for their multiplication. Later, he symmetrizes the construction to get an $N\times N\times N^{\alpha}$ matrix multiply. We will give this starting construction and show how standard techniques can be used to obtain an $N\times N^{\alpha}\times N$ matrix multiply from his basic construction.

The multiplication of $A^{\prime\prime}$ and $B^{\prime\prime}$ will be derived from an algorithm which computes the product of $2\times 3$ and $3\times 2$ matrices with zeroes in some entries. In particular the matrices have the form:

and the algorithm is given by the trilinear form

When the algorithm given by (6) is applied recursively to $2^{M}\times 3^{M}$ and $3^{M}\times 2^{M}$ matrices (analogously to how Strassen’s algorithm is applied to do $2^{M}\times 2^{M}\times 2^{M}$ matrix multiply), we obtain an algorithm that can multiply matrices $A$ and $B$ with dimensions $2^{M}\times 3^{M}$ and $3^{M}\times 2^{M}$, respectively, where $A$ has $O(5^{M})$ nonzeroes, $B$ has $O(4^{M})$ nonzeroes, and these nonzeroes appear in a highly regular pattern (which can be easily deduced). This recursive application of (6) will result in polynomials in $x$ of degree $O(M)$, and additions and multiplications on such polynomials increase the overall time by an $M\cdot{\text{poly}}(\log M)$ factor. Therefore we can multiply these $A$ and $B$ with structured nonzeroes in $O(5^{M}\cdot{\text{poly}}(M))$ field operations.

The decomposition of $A^{\prime\prime}$ and $B^{\prime\prime}$ is performed as follows. We choose $A^{\prime}$ and $B^{\prime}$ to have dimensions $2^{4M/5}\times 2^{M}$ and $2^{M}\times 2^{M/5}$, respectively, and such that all $2^{4M/5}\times 2^{4M/5}$ submatrices of $A^{\prime}$ and $2^{M/5}\times 2^{M/5}$ submatrices of $B^{\prime}$ are non-singular. Following Schönhage, we pick $A^{\prime}$ and $B^{\prime}$ to be rectangular Vandermonde matrices: the $i,j$ entry of $A^{\prime}$ is $(\alpha_{j})^{i-1}$, where $\alpha_{1},\alpha_{2},\ldots$ are distinct elements of the field; $B^{\prime}$ is defined analogously. Such matrices have three major advantages: (1) they can be succinctly described (with $O(2^{M})$ field elements), (2) multiplying these matrices with arbitrary vectors can be done extremely efficiently, and (3) inverting an arbitrary square submatrix can be done extremely efficiently. More precisely, $n\times n$ Vandermonde matrices can be multiplied with arbitrary $n$-vectors in $O(n\cdot{\text{poly}}(\log n))$ operations, and computing the inverse of an $n\times n$ Vandermonde matrix can be done in $O(n\cdot{\text{poly}}(\log n))$ operations (for references, see [CKY89, BP94]). In general, operations on Vandermonde matrices, their transposes, their inverses, and the transposes of inverses can be reduced to fast multipoint computations on univariate polynomials. For example, multiplying an $n\times n$ Vandermonde matrix with a vector is equivalent to evaluating a polynomial (with coefficients given by the vector) on the $n$ elements that comprise the Vandermonde matrix, which takes $O(n\log n)$ operations. This translates to $O(n\cdot{\text{poly}}(\log n))$ arithmetic operations.

The matrices $A$ and $B$ have dimensions $2^{M}\times 3^{M}$ and $3^{M}\times 2^{M}$, respectively, where $A$ has only $O(5^{M})$ nonzeroes, $B$ has only $O(4^{M})$ nonzeroes, and there is an optimal algorithm for multiplying $2\times 3$ (with 5 nonzeroes) and $3\times 2$ matrices (with 4 nonzeroes) that can be recursively applied to multiply $A$ and $B$ optimally, in $O(5^{M}\cdot{\text{poly}}(M))$ operations. Matrices $A$ and $B$ are constructed as follows: take any one-to-one mapping between the ${M\choose 4M/5}2^{M/5}$ columns of the input $A^{\prime\prime}$ and columns of the sparse $A$ with exactly $2^{4M/5}$ nonzeroes. For these columns $q$ of $A$ with $2^{4M/5}$ nonzeroes, we compute the inverse $A_{q}^{-1}$ of the $2^{4M/5}\times 2^{4M/5}$ minor $A_{q}$ of $A^{\prime}$ with rows corresponding to the nonzeroes in the column, and multiply $A_{q}^{-1}$ with column $q$ (in $2^{4M/5}\cdot{\text{poly}}(M)$ time). After these columns are processed, the rest of $A$ is zeroed out. Then, there is a one-to-one correspondence between columns of $A^{\prime\prime}$ and nonzero columns of $A^{\prime}\cdot A$. Performing a symmetric procedure for $B^{\prime\prime}$ (with the same mapping on rows instead of columns), we can decompose it into $B$ and $B^{\prime}$ such that there is a one-to-one correspondence between rows of $B^{\prime\prime}$ and nonzero rows of $B\cdot B^{\prime}$. It follows that this decomposition takes only $O({M\choose 4M/5}2^{4M/5}\cdot 2^{4M/5}\cdot{\text{poly}}(M))$ time. Since $5^{M}\approx{M\choose 4M/5}4^{4M/5}$ (within ${\text{poly}}(M)$ factors), this quantity is upper bounded by $5^{M}\cdot{\text{poly}}(M)$.

After $A$ and $B$ are constructed, the constant-sized algorithm for $2\times 3$ and $3\times 2$ mentioned above can be applied in the usual recursive way to multiply the sparse $A$ and $B$ in $O(5^{M}\cdot{\text{poly}}(M))$ operations; call this matrix $Z$. Because $A^{\prime}$ and $B^{\prime}$ are Vandermonde, the product $A^{\prime}\cdot Z\cdot B^{\prime}$ can be computed in $O(5^{M}\cdot{\text{poly}}(M))$ operations. Hence we have an algorithm for multiplying matrices of dimensions $2^{4M/5}\times{M\choose 4M/5}2^{4M/5}$ and ${M\choose 4M/5}2^{4M/5}\times 2^{M/5}$ that is explicit and takes $5^{M}\cdot{\text{poly}}(M)$ operations.

Call the above algorithm Algorithm 1. Observe Algorithm 1 also works when the entries of $A^{\prime\prime}$ and $B^{\prime\prime}$ are themselves matrices over the field. (The running time will surely increase in proportion to the sizes of the underlying matrices, but the bound on the number of operations on the entries remains the same.)

Up to this point, we have simulated Coppersmith’s construction completely, and have simply highlighted its efficiency. By exploiting the symmetries of matrix multiplication algorithms in a standard way, we can extract more algorithms from the construction. The trace identity tells us that

implying that the expression (6) can also be used to partially multiply a $3^{M}\times 2^{M}$ matrix $B$ with at most $4^{M}$ structured nonzeroes and “full” $2^{M}\times 2^{M}$ matrix $C$ in $5^{M}\cdot{\text{poly}}(M)$ operations, obtaining a $3^{M}\times 2^{M}$ matrix $A^{T}$ with at most $5^{M}$ nonzeroes. In our Algorithm 1, we have a decomposition of $A$ and $B$; in terms of the trace, we can derive:

This can be applied to obtain an algorithm for ${M\choose 4M/5}2^{4M/5}\times 2^{M/5}\times 2^{4M/5}$ matrix multiplication, as follows. Given input matrices $B^{\prime\prime}$ and $C^{\prime\prime}$ of the respective dimensions, we decompose $B^{\prime\prime}$ into a $3^{M}\times 2^{M}$ $B$ with $O(4^{M})$ nonzeroes and $2^{M}\times 2^{M/5}$ Vandermonde $B^{\prime}$, as described above. Letting $A^{\prime}$ be a Vandermonde $2^{4M/5}\times 2^{M}$ matrix, we compute the matrix $C:=B^{\prime}\cdot C^{\prime\prime}\cdot A^{\prime}$ in at most $4^{M}\cdot{\text{poly}}(M)$ operations. Noting that $C$ is $2^{M}\times 2^{M}$, we can then multiply $B$ and $C$ in $5^{M}\cdot{\text{poly}}(M)$ operations. This results in a $3^{M}\times 2^{M}$ matrix $A^{T}$ with at most $5^{M}$ nonzeroes. The final output $A^{\prime\prime}$ is obtained by using the one-to-one mapping to extract the appropriate ${M\choose 4M/5}2^{4M/5}$ rows from $A^{T}$, and multiplying each such row by the appropriate inverse minor of $A^{\prime}$ (corresponding to the nonzeroes of that row). This takes at most ${M\choose 4M/5}2^{4M/5}\cdot 2^{M}\cdot{\text{poly}}(M)\leq 5^{M}\cdot{\text{poly}}(M)$ operations. Call this Algorithm 2.

From Algorithm 2 we immediately obtain an algorithm for $2^{4M/5}\times 2^{M/5}\times{M\choose 4M/5}2^{4M/5}$ matrix multiplication as well: given input matrices $(C^{\prime\prime})^{T}$ and $(B^{\prime\prime})^{T}$ of te respective dimensions, simply compute $B^{\prime\prime}\cdot C^{\prime\prime}$ using Algorithm 2, and output the transpose of the answer. Call this Algorithm 3.

Finally, by “tensoring” Algorithm 2 with Algorithm 3, we derive an algorithm for matrix multiplication with dimensions

That is, we divide the two input matrices of large dimensions into blocks of $2^{4M/5}\times 2^{M/5}$ and $2^{M/5}\times{M\choose 4M/5}2^{4M/5}$ dimensions, respectively. We execute Algorithm 2 on the blocks, and call Algorithm 3 when the product of two blocks is needed.

As both Algorithm 2 and Algorithm 3 are explicit and efficient, their “tensorization” inherits these properties. Algorithm 2 uses $5^{M}\cdot{\text{poly}}(M)$ operations, and each operation can take up to $5^{M}\cdot{\text{poly}}(M)$ time (due to calls to Algorithm 3). Therefore, we can perform a $5^{M}\times 4^{2M/5}\times 5^{M}$ matrix multiply over fields with $2^{{\text{poly}}(M)}$ elements, in $5^{2M}\cdot{\text{poly}}(M)$ time. Setting $n=\log(M)/\log(5)$, the algorithm runs in $n^{2}\cdot{\text{poly}}(\log n)$ time for fields with $2^{{\text{poly}}(\log n)}$ elements.