Inherent limitation of Switching Lemma for finer lower bounds

Question

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)}})$

Answer 1

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.