Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-185 | 29th December 2012 23:03

Tight Bounds for Monotone Switching Networks via Fourier Analysis



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 ’99). 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.

ISSN 1433-8092 | Imprint