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?
Why is $\Omega(\log\log n)$ a lower bound for the depth of polynomial-width circuits computing parity?
lower bounds;circuits