Monotone Circuits for Matching Require Linear Depth

Ran Raz; Avi Wigderson

doi:10.1145/146637.146684

Monotone Circuits for Matching Require Linear Depth

Ran Raz, Avi Wigderson

Research output: Contribution to journal › Article › peer-review

102 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 language	English (US)
Pages (from-to)	736-744
Number of pages	9
Journal	Journal of the ACM (JACM)
Volume	39
Issue number	3
DOIs	https://doi.org/10.1145/146637.146684
State	Published - Jan 7 1992
Externally published	Yes

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

Access to Document

10.1145/146637.146684

Cite this

@article{cca84a7ed08e434ab8bf40c5a643a9cc,

title = "Monotone Circuits for Matching Require Linear Depth",

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.",

keywords = "circuit depth, monotone computation, perfect matching",

author = "Ran Raz and Avi Wigderson",

year = "1992",

month = jan,

day = "7",

doi = "10.1145/146637.146684",

language = "English (US)",

volume = "39",

pages = "736--744",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "3",

}

TY - JOUR

T1 - Monotone Circuits for Matching Require Linear Depth

AU - Raz, Ran

AU - Wigderson, Avi

PY - 1992/1/7

Y1 - 1992/1/7

N2 - 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.

AB - 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.

KW - circuit depth

KW - monotone computation

KW - perfect matching

UR - http://www.scopus.com/inward/record.url?scp=0026888974&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026888974&partnerID=8YFLogxK

U2 - 10.1145/146637.146684

DO - 10.1145/146637.146684

M3 - Article

AN - SCOPUS:0026888974

SN - 0004-5411

VL - 39

SP - 736

EP - 744

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 3

ER -

Monotone Circuits for Matching Require Linear Depth

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this