ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-185 | 29th December 2012 23:03

Tight Bounds for Monotone Switching Networks via Fourier Analysis

RSS-Feed

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 ’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