Theory of Computing
-------------------
Title     : Tight Bounds for Monotone Switching Networks via Fourier Analysis
Authors   : Siu Man Chan and Aaron Potechin
Volume    : 10
Number    : 15
Pages     : 389-419
URL       : https://theoryofcomputing.org/articles/v010a015

Abstract
--------

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 work 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.