2
$\begingroup$

I'm working on an exercise from The Nature of Computation concerning polynomial-width circuits computing parity. In particular the exercise asks to sketch a proof that the depth of such a circuit has the lower bound $\Omega(\log\log n)$ where $n$ is the number of input variables.

There is quite a large amount of literature on the subject flying around the web and I have seen claims for lower bounds of $\Omega(\log^* n)$ as well as $Ω(\log n/\log\log n)$. However the proofs of these statements completely defeat me.

Does anybody see a simpler way to arrive at the desired result?

$\endgroup$
  • $\begingroup$ Presumably the exercise contains some hints, or its location serves as a hint – maybe some material in the preceding section or sections is relevant. Otherwise it's hard to guess what proof the authors had in mind. $\endgroup$ – Yuval Filmus Dec 27 '16 at 18:07
  • $\begingroup$ Unfortunately this isn't the case. $\endgroup$ – Sebastian Oberhoff Dec 27 '16 at 18:23
1
$\begingroup$

After some more thought here is my own attempt at a solution:

Assume for contradiction that the depth $d$ isn't $\Omega(\log \log n)$. Then it must be that

$\forall C,N:\exists n > N: d < C \lg \lg n$.
(Base 2 is an arbitrary choice for the logarithm.)

In particular if $C = \frac 1 2$ then

$\forall N: \exists n > N: 2^{2^{2d}} < n$.

At this point the Switching Lemma is required. The Switching Lemma is stated in The Nature of Computation as follows:

Consider a circuit with $n$ inputs $x_1,...,x_n$ consisting of a layer of OR gates which feed into a single AND gate, where both types of gates have arbitrary fan-in. Now suppose that we randomly restrict this circuit as follows. For each variable $x_i$, with probability $1-n^{-\frac 1 2}$ we set $x_i$ randomly to true or false, and with probability $n^{-\frac 1 2}$ we leave it unset. For any constant $a$, if there are $O(n^a)$ OR gates, then with probability $1-o(n^{-a})$ the resulting circuit can be expressed as a layer of a constant number of AND gates, which feed into a single OR gate.

The Switching Lemma is symmetric with respect to AND and OR. So every time the Switching Lemma is applied the top two layers are switched and the second and third layer can then be merged into a single layer leaving a circuit of depth $d-1$. Thus after applying the Switching Lemma $d-2$ times the circuit has depth $2$ remaining.
Applying the Switching Lemma one last time no longer reduces the depth of the circuit but does leave a circuit that only depends on a constant number of inputs. (This follows from details of the proof of the Switching Lemma.)
At the same time the number of remaining unset variables is

$\sim n^{\frac{1}{2^d}} > (2^{2^{2d}})^{\frac{1}{2^d}} = 2^{\big(\frac{2}{\sqrt 2}\big)^{2d}} = 2^{2^d}$.

And since a previous result established that Parity isn't in $AC^0$, we know that $d$ and for that matter $2^{2^d}$ eventually exceeds any constant.
If we were then to set those variables on which the circuit still depends, we'd arrive at a constant circuit computing Parity with some variables still unset, which yields a contradiction.
Also note that the width remained polynomial since the Switching Lemma increases it by a constant factor $m$ each time it is applied. So the width is multiplied by

$m^{d-1} < m^{\frac{1}{2} \lg \lg n} = (\lg n)^{\frac{1}{2} \lg m} = poly(n)$.

Hence $d = \Omega(\log \log n)$.

I want to point out however that this proof is fairly out of my personal comfort zone. So I don't want to make any guarantees.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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