Monotone Circuits for Matching Require Linear Depth

Ran Raz, Avi Wigderson

Research output: Contribution to journalArticle

80 Scopus citations

Abstract

It is proven that monotone circuits computing the perfect matching function on n-vertex graphs require Ω1992 depth. This implies an exponential gap between the depth of monotone and nonmonotone circuits.

Original languageEnglish (US)
Pages (from-to)736-744
Number of pages9
JournalJournal of the ACM (JACM)
Volume39
Issue number3
DOIs
StatePublished - Jan 7 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • circuit depth
  • monotone computation
  • perfect matching

Fingerprint Dive into the research topics of 'Monotone Circuits for Matching Require Linear Depth'. Together they form a unique fingerprint.

  • Cite this