Monotone circuits for matching require linear depth

Ran Raz, Avi Wigderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Scopus citations

Abstract

It is shown that every monotone circuit that decides if an n node graph has a matching of size n/3 must have depth Ω(n). The proof uses the a communication complexity approach. It consists of a sequence of simple reductions from the probabilistic communication complexity of the set disjointness function, for which a linear lower bound is known.

Original languageEnglish (US)
Title of host publicationProc 22nd Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages287-292
Number of pages6
ISBN (Print)0897913612, 9780897913614
DOIs
StatePublished - Jan 1 1990
Externally publishedYes
EventProceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA
Duration: May 14 1990May 16 1990

Publication series

NameProc 22nd Annu ACM Symp Theory Comput

Other

OtherProceedings of the 22nd Annual ACM Symposium on Theory of Computing
CityBaltimore, MD, USA
Period5/14/905/16/90

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Monotone circuits for matching require linear depth'. Together they form a unique fingerprint.

  • Cite this

    Raz, R., & Wigderson, A. (1990). Monotone circuits for matching require linear depth. In Proc 22nd Annu ACM Symp Theory Comput (pp. 287-292). (Proc 22nd Annu ACM Symp Theory Comput). Publ by ACM. https://doi.org/10.1145/100216.100253