Separation of the monotone NC hierarchy

Ran Raz, Pierre McKenzie

Research output: Contribution to journalConference articlepeer-review

38 Scopus citations


We prove tight lower bounds, of up to nε, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. monotone-NC≠monotone-P. 2. For all i≥1, monotone-NCi≠monotone-NCi+1. 3. More generally: For any integer function D(n), up to nε (for some ε>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·D(n) (for some constant Const). Only a separation of monotone. NC1 from monotone-NC2 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 Ω(log2n). 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≤nε, we get a tight lower bound of Ω(k log n). Only a bound of Ω(k) was previously known.

Original languageEnglish (US)
Pages (from-to)234-243
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 38th IEEE Annual Symposium on Foundations of Computer Science - Miami Beach, FL, USA
Duration: Oct 20 1997Oct 22 1997

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture


Dive into the research topics of 'Separation of the monotone NC hierarchy'. Together they form a unique fingerprint.

Cite this