<p>I think you can't beat the $\exp(n^{\Omega(1/d-1)})$ lower bound. Here's a construction that should work for computing parities:</p>

<p>In order to compute parity of $n$ variables, partition them into groups of size $t \approx n^{1/d}$, compute parity of each group and recursively compute the parity of parities. That is, start with a parity tree of fan-out $t$. The depth of this tree would be $d$.</p>

<p>Then, replace each parity gate with a CNF or DNF or size $\approx \exp(t)$. This way you get a circuit of depth $2d$. It is possible to alternate between CNFs and DNFs at different levels so the circuit collapses to depth $d$. This way you get a depth $d$ circuit of size $\approx \exp(n^{1/d})$ that computes the parity of $n$ bits.</p>

<p>Now, since switching lemma is tight for the parity function, you shouldn't hope to get a better lower bound for more sophisticated functions just relying on that.</p>

CC BY-SA 3.0
2013-06-23T03:50:49.340Z
Your (classical) construction applies to arbitrary functions in NC$^1$, and in fact to arbitrary functions computable by polysize formulas.
Yuval Filmus
CC BY-SA 3.0
2013-06-23T03:01:58.603Z
2013-06-23T14:59:31.893Z
2013-06-23T14:59:31.893Z
Mahdi Cheraghchi
<p>The Switching Lemma is the one of the classic and most basic tools to prove concrete circuit lower bounds. We will only consider AC$^{0}$ circuits.</p>

<p>The Switching Lemma claims that we can get a shallow circuit by restricting most input wires at random. More precisely,</p>

<blockquote>
  <p><strong>Lemma</strong> (Håstad’s switching lemma)
  Suppose $f$ is expressible as a $k$-DNF, and let $\rho$ denote a random restriction that assigns random
  values to $t$ randomly selected input bits. Then for every $s$,
  $$Pr[f|\rho \text{ is not expressible as $s$-CNF} ]\leq (\frac{(n − t)k^{10}}{n})^{s/2}$$
  where $f|\rho$ denotes the function f restricted to the partial assignment.</p>
</blockquote>

<p>My  question is about the reason why this lemma is NOT applicable to derive <em>finer lower bounds</em> of constant depth $d$ circuit complexity. For example, the PARITY function has a bound of $2^{\Omega (n^{1/(d-1)})}$.  Why do we fail to obtain  bounds such as $2^{\Omega (n^{1/(\sqrt{d})})}$,$2^{\Omega (n^{1/(\log{d})})}$, or stronger $2^{\frac{n}{\text{polylog}(n)}}$ for some boolean function?</p>

<p>It seems that the number of remaining so called <em>star variables</em>, which are not be fixed by restrictions, is too small to be considered as "an input size".</p>

<blockquote>
  <p>Let $F(s(n),C)$ be the Maximum number of <em>star variables</em> to reduce a circuit with depth $d$ and size $s(n)$ and $n$ input wires to a depth-$2$ circuit, that is, DNF or CNF. Let $F(s(n))=\min_{C} F(s(n),C)$. What are upper bounds and lower bounds as tight as we can at this moment for the following concrete $s(n)$s?</p>
  
  <p>$s(n)=F(2^{Cn^{1/(\sqrt{d})}})$ or $F(2^{Cn^{1/(\log{d})}})$ or $F(2^{\frac{n}{\text{polylog}(n)}})$</p>
</blockquote>

CC BY-SA 3.0
2013-06-23T08:28:20.790Z
I have fixed many of the typos and formatting problems in the above, but haven't changed the mathematics, other than inserting a missing $\rho$.  Please check.
András Salamon
<cc.complexity-theory><co.combinatorics><circuit-complexity>
Inherent limitation of Switching Lemma for finer lower bounds
junyu
# Inherent limitation of Switching Lemma for finer lower bounds

(Asked by: username_0 on 2013-06-23)

The Switching Lemma is the one of the classic and most basic tools to prove concrete circuit lower bounds. We will only consider AC$^{0}$ circuits.

The Switching Lemma claims that we can get a shallow circuit by restricting most input wires at random. More precisely,

> **Lemma** (Håstad’s switching lemma)
> Suppose $f$ is expressible as a $k$-DNF, and let $\rho$ denote a random restriction that assigns random
> values to $t$ randomly selected input bits. Then for every $s$,
> $$Pr[f|\rho \text{ is not expressible as $s$-CNF} ]\leq (\frac{(n − t)k^{10}}{n})^{s/2}$$
> where $f|\rho$ denotes the function f restricted to the partial assignment.

My question is about the reason why this lemma is NOT applicable to derive *finer lower bounds* of constant depth $d$ circuit complexity. For example, the PARITY function has a bound of $2^{\Omega (n^{1/(d-1)})}$. Why do we fail to obtain bounds such as $2^{\Omega (n^{1/(\sqrt{d})})}$,$2^{\Omega (n^{1/(\log{d})})}$, or stronger $2^{\frac{n}{\text{polylog}(n)}}$ for some boolean function?

It seems that the number of remaining so called *star variables*, which are not be fixed by restrictions, is too small to be considered as "an input size".

> Let $F(s(n),C)$ be the Maximum number of *star variables* to reduce a circuit with depth $d$ and size $s(n)$ and $n$ input wires to a depth-$2$ circuit, that is, DNF or CNF. Let $F(s(n))=\min\_{C} F(s(n),C)$. What are upper bounds and lower bounds as tight as we can at this moment for the following concrete $s(n)$s?
>
> $s(n)=F(2^{Cn^{1/(\sqrt{d})}})$ or $F(2^{Cn^{1/(\log{d})}})$ or $F(2^{\frac{n}{\text{polylog}(n)}})$

**Tags:** cc.complexity-theory, co.combinatorics, circuit-complexity

> **Comments:**
> **username_1**: I have fixed many of the typos and formatting problems in the above, but haven't changed the mathematics, other than inserting a missing $\rho$.  Please check.  

---

## 1 answers

### Answer by username_2 on 2013-06-23. Score: 6

I think you can't beat the $\exp(n^{\Omega(1/d-1)})$ lower bound. Here's a construction that should work for computing parities:

In order to compute parity of $n$ variables, partition them into groups of size $t \approx n^{1/d}$, compute parity of each group and recursively compute the parity of parities. That is, start with a parity tree of fan-out $t$. The depth of this tree would be $d$.

Then, replace each parity gate with a CNF or DNF or size $\approx \exp(t)$. This way you get a circuit of depth $2d$. It is possible to alternate between CNFs and DNFs at different levels so the circuit collapses to depth $d$. This way you get a depth $d$ circuit of size $\approx \exp(n^{1/d})$ that computes the parity of $n$ bits.

Now, since switching lemma is tight for the parity function, you shouldn't hope to get a better lower bound for more sophisticated functions just relying on that.

> **Comments:**
> **username_3**: Your (classical) construction applies to arbitrary functions in NC$^1$, and in fact to arbitrary functions computable by polysize formulas.  

---

