Separation of the monotone NC hierarchy
Authors:
- P. McKenziePMP. McKenzie
- 23 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 31 (02725428) , 234-243
Abstract
We prove tight lower bounds, of up to n/sup /spl epsiv//, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. Monotone-NC/spl ne/monotone-P. 2. /spl forall/i/spl ges/1, monotone-NC/sup i//spl ne/monotone-NC/sup i+1/. 3. More generally: For any integer function D(n), up to n/sup /spl epsiv// (for some /spl epsiv/>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const/spl middot/D(n) (for some constant Const). Only a separation of monotone-NC/sup 1/ from monotone-NC/sup 2/ was previously known. Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of-this class. As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1. For st-connectivity, we get a tight lower bound of /spl Omega/(log/sup 2/ n). That is, we get a new proof for Karchmer-Wigderson's theorem, as an immediate corollary of our general result. 2. For the k-clique function, with k/spl les/n/sup /spl epsiv//, we get a tight lower bound of /spl Omega/(k log n). Only a bound of /spl Omega/(k) was previously known.Keywords
This publication has 25 references indexed in Scilit:
- A lower bound for the monotone depth of connectivity2002
- Upper and lower bounds for tree-like cutting planes proofs2002
- Communication complexity towards lower bounds on circuit depth2002
- Counting bottlenecks to show monotone P≠NP2002
- Modular coloring formulas are hard for cutting planes proofs1996
- Lower bounds for cutting planes proofs with small coefficients1995
- Monotone circuits for matching require linear depthJournal of the ACM, 1992
- Monotone circuits for matching require linear depth1990
- The gap between monotone and non-monotone circuit complexity is exponentialCombinatorica, 1988
- Some complexity questions related to distributive computing(Preliminary Report)1979