In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide whether there is a path between all $n^2$ pairs $(s,t)$ of vertices. In its special case, STCONN, the task is only for one fixed pair $(s,t)$ of vertices. I am interested in the size of monotone circuits with fanin-2 AND and OR gates solving STCONN.
QUESTION: Does STCONN require monotone boolean circuits of size $\Omega(n^3)$?
What I know is:
- STCONN, and even CONN, can be solved by monotone circuits of size $O(n^3)$: use well known dynamic programming algorithms of Bellman-Ford for STCONN, and by Floyd-Warshall for CONN.
- Every monotone circuit for STCONN has depth $\Omega(\log^2 n)$: Karchmer-Wigderson (1990), Grigni-Sipser (1995). By binary search, this depth is also enough.
- Every monotone circuit for CONN has size $\Omega(n^3)$: CONN has almost the same monotone complexity as boolean multiplication of two boolean matrices, and this latter problem is shown, by Paterson (1975) and by Mehlhorn-Galil (1976), to require $\Omega(n^3)$ gates.
But what about the size of monotone circuits for STCONN? Is this still an open problem? I guess - it is, but would be happy to hear the opposite.
ADDED (on 9.10.2012) My question is related to the question about the status of tropical circuit complexity of "weighted" STCONN (the shortest $s$-$t$ path problem); see my answer; a tropical circuit is a circuit with fanin-2 Min and Plus gates. Suppose we have a 0/1 optimization problem $f(x)=\min_{S\in{\cal F}}\sum_{i\in S}x_i$, where ${\cal F}$ is a family of feasible solutions, and $x_i$'s are real numbers. A "boolean version" of this problem is a monotone boolean function $f_B(x)=\bigvee_{S\in{\cal F}}\bigwedge_{i\in S}x_i$. In the case of the shortest $s$-$t$ path problem, $f_B$ is STCONN.
If the domain of $f(x)$ contains $0$ and $\infty$, then the minimum size of a tropical circuit for $f(x)$ is at least the minimum size of a monotone boolean circuit for $f_B(x)$. This holds because the mapping $h:\{0,\infty\}\to\{0,1\}$ given by $h(0):=1$ and $h(\infty):=0$ is a homomorphish from the semiring $(\{o,\infty\},\min,+)$ to the boolean semiring. But lower bounds for tropical circuits could come easier than for monotone boolean circuits: the domain now is huge (real numbers), and Min does not distribute over Plus. Hence, an ``easier'' question:
Does the shortest $s$-$t$ paths problem requires tropical circuits of size $\Omega(n^3)$?
Another model weaker than monotone boolean circuits and tropical circuits is that of monotone arithmetic circuits: here no produced monomials can be cancelled later. We can associate with the weighted STCONN a multilinear polynomial $P(x)$ by taking one monomial for each simple $s$-$t$ path. Hence, yet ``simpler'' question:
Does $P(x)$ require monotone arithmetic circuits of size $\Omega(n^3)$?
ADDED (23.01.2013): The list of known results above is not complete: Aaron Potechin has also shown that directed STCONN requires monotone switching networks of size $n^{\Omega(\log n)}$. Each such network is an undirected graphs with two distinguished source and target nodes, an with edges labeled by variables. When input vector arrives, all edges evaluated to $0$ are removed, and the vector is accepted iff there is a source-target path in the remaining subgraph. In contrast, is we would allow a network be directed then even directed STCONN can be solved (using similar construction as here) by a monotone network of size $O(n^4)$, even by an acyclic network. This is the largest known gap between monotone directed and undirected networks!
CORRECTION (on 21.05.2014): I was wrong with item 3 above: the lower bound $\Omega(n^3)$ for CONN is also not known! The bound on matrix product only gives such a lower bound for APCONN (all-pairs connectivity): this is a set of $n^2$ boolean functions $f_{ij}$ outputing $1$ iff there is a path between nodes $i$ and $j$. The (single-output) function CONN is the AND of all $f_{ij}$. Note that circuits computing CONN need not to compute APCONN: the circuit for CONNN needs not to compute the functions $f_{ij}$ on separate output gates.
ADDON (on 21.05.2014): Lower bounds on the monotone depth of CONN are also known: by improving an earlier bound $\Omega(n^{3/2}n/\ln\ln n)$ of Yao (1994), Goldman and Hastad (1998) proved an almost optimal bound of $\Omega(\ln^2/\ln\ln n)$. Interestingly, these bounds were proved not by using the Karchmer-Wigderson games (as it was for STCONN) but rather a form of Razboro's approximation method.
ANSWER (on 21.05.2014): My 3-rd (yet ``simpler'') question indeed has a simple answer: monotone arithmetic circuits for the STCONN polynomial $P(x)$ require even exponential size. This holds because: (1) every such circuit must also compute the Hamilton s-t path polynomial HP (monomials are s-t path containing all nodes), and (2) HP requires monotone arithmetic circuits of exponential size (a simple covering-by-rectangles argument since nothing can be cancelled in such circuits).
