Revised: January 22, 2013
Published: November 4, 2014
Abstract: [Plain Text Version]
We prove tight size bounds on monotone switching networks for the NP-complete problem of $k$-clique, and for an explicit monotone problem by analyzing a pyramid structure of height $h$ for the P-complete problem of generation. This gives alternative proofs of the separations of m-NC from m-P and of m-NC$^i$ from m-NC$^{i+1}$, different from Raz--McKenzie (Combinatorica 1999). The enumerative-combinatorial and Fourier analytic techniques in this paper are very different from a large body of work on circuit depth lower bounds, and may be of independent interest.
An earlier version of this paper appeared in the Proceedings of the 44th ACM Symp. on Theory of Computing, pp. 495-504, 2011.