Tight Bounds for Monotone Switching Networks via Fourier Analysis
by
Revised: January 22, 2013
Published: November 4, 2014
[PDF (366K)] [PS (1657K)] [Source ZIP]
Keywords: lower bounds, space complexity, parallel complexity, monotone complexity, switching networks, Fourier analysis
ACM Classification: F.1.3
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40

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.