SPECIAL ISSUE: ANALYSIS OF BOOLEAN FUNCTIONS Tight Bounds for Monotone Switching Networks via Fourier Analysis

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-NCi from m-NCi+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. ACM Classification: F.1.3 AMS Classification: 68Q17, 68Q15, 68Q10 Key words and phrases: lower bounds, space complexity, parallel complexity, monotone complexity, switching networks, Fourier analysi