\(
\def\<#1>{\left<#1\right>}
\def\f{\mathcal{F}}
\newcommand{\R}{\mathcal{R}}
\def\aveDeg#1#2{d_{#2}(#1)}
\def\minDeg#1#2{\delta_{#2}(#1)}
\def\proj#1#2{{#1}_{#2}}
\def\fact#1#2{f_{#1}\left(#2\right)}
\newcommand{\ffact}[1]{f_{#1}}
\def\euler{\mathrm{e}}
\def\rect{{\cal R}}
\def\dens#1{\alpha_{#1}}
\)

## 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