Is there a simple example of a monotone Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone circuit? Ideally, I'd be especially interested in a simple example where there is an exponential gap between the size of the smallest monotone circuit and the size of the smallest (not necessarily monotone) circuit.
Razborov's famous result shows that the $k$-clique function requires a monotone circuit of size $\Omega(n^k)$. In particular, we treat $x$ as the adjacency matrix of a graph and define $f(x)=1$ if the graph has a $k$-clique or 0 otherwise. However, this doesn't appear to provide a large gap between monotone circuit complexity and ordinary circuit complexity: the clique function can be computed by a monotone circuit of size $O(n^k)$, and the best known non-monotone circuit has size $O(n^{\omega k/3}) \approx O(n^{0.8k})$, where $\omega = 2.373...$ is the constant for matrix multiplication. This is not a very large gap: $O(n^k)$ vs $O(n^{0.8k})$. In particular, for choices of $k$ where the non-monotone complexity is polynomial, so is the monotone complexity.
Based on Razborov's result, Tardos has defined a function $\varphi$ that does have this exponential gap. However, $\varphi$ is fairly complex to even define: one must first introduce the Lovász number of a graph, then discuss how to approximate this number in polynomial time using linear programming, then show how to adjust the result to obtain the definition of the resulting function $\varphi$. In other words, the Tardos $\varphi$ function is not particularly simple to define.
So is there a suitable example that is simple/easy to define, and has a large gap between its monotone and non-monotone circuit complexity?
