<p>Thanks, Kaveh, for wishing to look at chapters on proof complexity!</p>

<p>Concerning Robin's question, first that note $AC^0$ <b>contains</b> 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$.</p>

<p>I shortly discussed the issue of getting <b>explicit</b> 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$ <b>can</b> 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.</p>

<p>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.</p>

<p>Proof: Given a formula for $F(X)$ with $s$ leaves, select in each block $X_i$ a variable which appears the <b>smallest</b> 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 <b>smaller</b> 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.</p>

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

CC BY-SA 3.0
2011-07-03T14:42:24.397Z
2011-07-09T16:15:30.330Z
2011-07-09T16:15:30.330Z
Stasys
<p>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.  </p>

<p>Actually, the Allender-Koucky phenomenon arises also in other context - in graph complexity. Say that a circuit of $2n$ variables <i>represents</i> 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 <b>monotone</b> $\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 <b>non-monotone</b> 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.   </p>

CC BY-SA 3.0
2011-07-02T19:46:46.970Z
Welcome to cstheory. :) (btw, your [new book](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html) looks quite interesting, unfortunately I am not a native English speaker so can't help with proof-reading it.)
Kaveh
CC BY-SA 3.0
2011-07-02T20:10:37.323Z
Actually, any comments/critics on the contents/references and so on are at this point also very important. The current version is 
[here](http://www.thi.informatik.uni-frankfurt.de/~jukna/BFC-book/). User: friend Password: catchthecat
Stasys
CC BY-SA 3.0
2011-07-02T20:36:37.260Z
Thank you :) I am going to read the final chapters about propositional proof complexity.
Kaveh
CC BY-SA 3.0
2011-07-02T20:55:38.020Z
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
CC BY-SA 3.0
2011-07-02T19:24:25.867Z
2011-07-02T19:24:25.867Z
Stasys
<p><strong>Question:</strong></p>

<blockquote>
  <p>What is the best known formula size lower bound for an explicit function in AC<sup>0</sup>? Is there an explicit function with an $\Omega(n^2)$ lower bound?</p>
</blockquote>

<p><strong>Background:</strong></p>

<p>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}.</p>

<p>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.</p>

<p>However, these two functions are not in AC<sup>0</sup>. I'm wondering if we know an explicit function in AC<sup>0</sup> 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<sup>0</sup>, so I'm looking for a lower bound for an explicit AC<sup>0</sup> function that is better than $\Omega(n^2/\log n)$, preferably $\Omega(n^2)$.</p>

<p><strong>Further reading:</strong></p>

<p>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.</p>

CC BY-SA 3.0
2011-06-28T23:41:33.513Z
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
CC BY-SA 3.0
2011-06-29T00:08:35.967Z
@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
CC BY-SA 3.0
2011-06-29T02:24:13.537Z
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
CC BY-SA 3.0
2011-07-08T02:41:32.573Z
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
<cc.complexity-theory><lower-bounds><circuit-complexity><formulas>
Formula size lower bounds for AC0 functions
Robin Kothari
# Formula size lower bounds for AC0 functions

(Asked by: username_0 on 2011-06-28)

**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 username_2 Jukna. A draft of the book is available for free on his website.

**Tags:** cc.complexity-theory, lower-bounds, circuit-complexity, formulas

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1: 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).  
> **username_1**: 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.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2011-07-02. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_1**: Welcome to cstheory. :) (btw, your [new book](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html) looks quite interesting, unfortunately I am not a native English speaker so can't help with proof-reading it.)  
> **username_2**: Actually, any comments/critics on the contents/references and so on are at this point also very important. The current version is  [here](http://www.thi.informatik.uni-frankfurt.de/~jukna/BFC-book/). User: friend Password: catchthecat  
> **username_1**: Thank you :) I am going to read the final chapters about propositional proof complexity.  
> **username_0**: 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.  

---

### Answer by username_2 on 2011-07-03. Score: 12

Thanks, username_1, 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$.


---

