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 decidewhether 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)$: usewell 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 depthis 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 offeasible solutions, and $x_i$'s are real numbers. A boolean version ofthis 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 circuitfor $f(x)$ is at least the minimum size of a monotone boolean circuitfor $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 ofmonotone arithmetic circuits: here no produced monomials can becancelled 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 STCONNrequires monotone switching networks of size $n^{\Omega(\log n)}$.Each such network is an undirected graphs with twodistinguished 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 remainingsubgraph. In contrast, is we would allow a network be directed theneven directed STCONN can be solved (using similar construction as here)by a monotone network of size $O(n^4)$, even by anacyclic 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).  
Monotone complexity of s-t connectivity
cc.complexity theory;circuit complexity;lower bounds;dynamic programming;monotone