Directed STCONN requires large monotone span programs

As shown in Chapter 8 "Span Programs" (Lemmas 8.5 and 8.6), there is an explicit monotone Boolean function $f$ of $n$ variables (the odd factor function) such that $f$ requires monotone circuits of size $n^{\Omega(\log n)}$ but can be computed by a monotone span program of size $n$. Research Problem 8.7 asked: Do there exist functions admitting polynomial-size monotone circuits which require super-polynomial size monotone span programs? This question was answered in the affirmative by Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook.

Let $\vec{K}_n$ be a complete directed graph on $\{1,\ldots,n\}$, each of whose edges $(i,j)$ has its associated Boolean variable $x_{i,j}$. Every $0$-$1$ assignment to these variables defines a subgraph $G_x$ of $\vec{K}_n$. The $s$-$t$ connectivity function STCONN$_{n}$ accepts $x$ iff there is a path from node $1$ to node $n$ in $G_x$.

The Boolean version of the Bellman-Ford-Moore dynamic programming algorithm has $O(n^3)$ gates and computes STCONN$_{n}$. On the other hand, we have the following lower bound for monotone span programs computing this function.

Theorem ([1]): The function STCONN$_{n}$ requires $n^{\Omega(\log n)}$ size monotone span programs over ${\mathbb R}$.

Thus, the powers of monotone circuits and of monotone span programs are incomparable!

References:

R. Robere, T. Pitassi, B. Rossman and S. A. Cook: Exponential Lower Bounds for Monotone Span Programs, in: IEEE 57th Ann. Symp. on Foundations of Comput. Sci. (FOCS), 2016. Extended version: ECCC Report Nr. 16, 2016.

S. Jukna, December 9, 2021