Monotone circuits for matching require linear depth

Ran Raz, Avi Wigderson

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

31 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 - 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

  • General Engineering

Fingerprint

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

Cite this