Simple example of exponential gap between monotone and non-monotone circuits

Question

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?

Answer 1

AFAIU XOR-SAT and perfect matching are simple to understand examples that have polynomial circuit and super polynomial lower bound for monotone circuits.

On the contrary, there are examples where this gap does not exist but you may feel like it does, so they give you a better intuition on the power of non monotone circuits. For example, to compute Majority function with non monotone circuit you just need a full adder, and to check if the sum is greater than $n/2$. However, with monotone circuit it is not obvious how to make a polynomial size circuit, as the only obvious way is to go through all $n/2$ subsets and test if they are all 1's, which is definitely not a polynomial size circuit.