Tight Bounds for Monotone Switching Networks via Fourier Analysis
by
Revised: January 22, 2013
Published: November 4, 2014
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.