Formula size lower bounds for AC0 functions

Question

Question:

What is the best known formula size lower bound for an explicit function in AC⁰? Is there an explicit function with an $\Omega(n^2)$ lower bound?

Background:

Like most lower bounds, formula size lower bounds are hard to come by. I am interested in formula size lower bounds over the standard universal gate set {AND, OR, NOT}.

The best known formula size lower bound for an explicit function over this gate set is $\Omega(n^{3-o(1)})$ for a function defined by Andreev. This bound was shown by Håstad, improving Andreev's lower bound of $\Omega(n^{2.5-o(1)})$. Another explicit lower bound is Khrapchenko's $\Omega(n^2)$ lower bound for the parity function.

However, these two functions are not in AC⁰. I'm wondering if we know an explicit function in AC⁰ with a quadratic (or better) lower bound. The best bound I am aware of is the $\Omega(n^2/\log n)$ lower bound for the Element Distinctness function, as shown by Nechiporuk. Note that the element distinctness function is in AC⁰, so I'm looking for a lower bound for an explicit AC⁰ function that is better than $\Omega(n^2/\log n)$, preferably $\Omega(n^2)$.

Further reading:

An excellent resource on the topic is "Boolean Function Complexity: Advances and Frontiers" by Stasys Jukna. A draft of the book is available for free on his website.

Answer 1

A nice question! Khrapchenko can definitely not give quadratic lower bounds for $AC^0$ functions. His lower bound is in fact at least square of average sensitivity. And all functions in $AC^0$ have poly-logarithmic average sensitivity. Subbotovskaya-Andreev can apparently also not give such a function because the argument they use (random restriction results in much smaller formulas) is exactly the reason forcing large $AC^0$ circuit size; Hastad's Switching Lemma (am not quite sure, just an intuition). The only hope is Nechiporuk. But his argument cannot give more than $n^2/\log n$, by information theoretic reasons. So, can it be that everything in $AC^0$ has formulas of quadratic (or even smaller) size? I don't believe in it, but couldn't quickly find a counterexample.

Actually, the Allender-Koucky phenomenon arises also in other context - in graph complexity. Say that a circuit of $2n$ variables represents a bipartite $n\times n$ graph $G$ on vertices $V=\{1,\ldots,2n\}$ if for every input vector $a$ with exactly two 1s is, say, positions $i$ and $j$ ($i\leq n$, $j>n$) the circuit accepts $a$ iff vertices $i$ and $j$ are adjacent in $G$. Problem: exhibit an explicit graph $G$ requiring at least $n^{\epsilon}$ gates to be represented by a monotone $\Sigma_3$-circuit. Seems like an innocent question (since most graphs require about $n^{1/2}$ gates. But any such graph would give us a boolean function of $2m=2\log n$ variables requiring non-monotone log-depth circuits of superlinear size (by results of Valiant). Thus, even proving $n^{\epsilon}$ lower bounds for depth-3 circuits may be a challenge.

Answer 2

Thanks, Kaveh, for wishing to look at chapters on proof complexity!

Concerning Robin's question, first that note $AC^0$ contains functions requiring formulas (and even circuits) of size $n^k$ for any constant $k$. This follows, say, from a simple fact that $AC^0$ contains all DNFs with constantly long monomials. Thus, $AC^0$ contains at least $\exp(n^k)$ distinct functions, for any $k$. On the other hand, we have at most about $\exp(t\log n)$ functions computable by formulas of size $t$.

I shortly discussed the issue of getting explicit lower bounds of $n^2$ or larger with Igor Sergeev (from Moscow university). One possibility could be to use Andreev's method, but applied to some another, easier computable function instead of Parity. That is, consider a function of $n$ variables of the form $F(X)=f(g(X_1),\ldots,g(X_b))$ where $b=\log n$ and $g$ is a function in $AC^0$ of $n/b$ variables; $f$ is some most complex function of $b$ variables (mere existence of $f$ is enough). We only need that the function $g$ cannot be "killed" in the following sense: if we fix all but $k$ variables in $X$, then it must be possible to fix all but one of the remaining variables of $g$ so that the obtained subfunction of $g$ is a single variable. Then applying Andreev's argument and using Hastad's result that the shrinking constant is at least $2$ (not just $3/2$ as earlier shown by Sybbotovskaya), the resulting lower bound for $F(X)$ will be about $n^3/k^2$. Of course, we know that every function in $AC^0$ can be killed by fixing all but $n^{1/d}$ variables, for some constant $d\geq 2$. But to get a $n^2$ lower bound it would be enough to find an explicit function in $AC^0$ which cannot be killed by fixing all but, say, $n^{1/2}$ variables. One should search for such a function in depth larger than two.

Actually, for the function $F(X)$ as above, one can obtain lower bounds about $n^2/\log n$ via simple greedy argument, no Nechiporuk, no Subbotovskaya and no random restrictions! For this, it is merely enough that the "inner function" g(Y) is non-trivial (depends on all its $n/b$ variables). Moreover, the bound holds for any basis of constant fanin-gates, not just for De Morgan formulas.

Proof: Given a formula for $F(X)$ with $s$ leaves, select in each block $X_i$ a variable which appears the smallest number of times as a leaf. Then set all remaining variables to the corresponding constants so that each $g(X_i)$ turns to a variable or its negation. The obtained formula will then be at least $n/b$ times smaller than the original formula. Thus, $s$ is at least $n/b=n/\log n$ times the formula size $2^b/\log b=n/\log\log n$ of $f$, that is, $s\geq n^{2-o(1)}$. Q.E.D.

To get $n^2$ or more, one has to incorporate Subbotovskaya-Hastad shrinking effect under random restrictions. A possible candidate could be some version of Sipser's function used by Hastad to show that depth-$(d+1)$ circuits are more powerful than those of depth $d$.