Question:

What is the best known formula size lower bound for an explicit function in AC0? 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 AC0. I'm wondering if we know an explicit function in AC0 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 AC0, so I'm looking for a lower bound for an explicit AC0 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.

  • Can the reason for lack of superlinear lowerbounds for $AC^0$ functions be some sort of self-reducibility for $AC^0$ functions? i.e. if we have a $n^{1+\epsilon}$ lowerbound (where $\epsilon$ is not dependent on the depth) then we get a superpoly lowerbound. – Kaveh Jun 28 '11 at 23:41
  • @Kaveh: I'm not sure I understand. We do already have an $\Omega(n^2/\log n)$ lower bound for a function in $AC^0$ (element distinctness). – Robin Kothari Jun 29 '11 at 0:08
  • Sorry, replace the superlinear with super-quadratic. I mean something similar to Allender-Koucky result for $TC^0$. The exponent for $AC^0$ might be bigger. Such a result may explain why it is difficult to find $AC^0$ lowerbounds for $AC^0$ functions. – Kaveh Jun 29 '11 at 2:24
  • It seems that any problem which is complete for $AC^0$ under Turing $NC^0$ reductions is strongly self-reducible, but this doesn't seem to give what I was expecting since the size of self-reduction can be polynomially large. – Kaveh Jul 8 '11 at 2:41
up vote 15 down vote accepted

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.

  • Welcome to cstheory. :) (btw, your new book looks quite interesting, unfortunately I am not a native English speaker so can't help with proof-reading it.) – Kaveh Jul 2 '11 at 19:46
  • Actually, any comments/critics on the contents/references and so on are at this point also very important. The current version is here. User: friend Password: catchthecat – Stasys Jul 2 '11 at 20:10
  • Thank you :) I am going to read the final chapters about propositional proof complexity. – Kaveh Jul 2 '11 at 20:36
  • 2
    Thanks a lot for the answer! If you do think of a function in $AC^0$ that you conjecture requires an $\Omega(n^2)$ sized formula, I'll be interested to know. – Robin Kothari Jul 2 '11 at 20:55

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$.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.