Monotone circuits for matching require linear depth

Ran Raz; Avi Wigderson

doi:10.1145/100216.100253

Monotone circuits for matching require linear depth

Ran Raz, Avi Wigderson

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proc 22nd Annu ACM Symp Theory Comput
Publisher	Publ by ACM
Pages	287-292
Number of pages	6
ISBN (Print)	0897913612, 9780897913614
DOIs	https://doi.org/10.1145/100216.100253
State	Published - 1990
Externally published	Yes
Event	Proceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA Duration: May 14 1990 → May 16 1990

Publication series

Name	Proc 22nd Annu ACM Symp Theory Comput

Other

Other	Proceedings of the 22nd Annual ACM Symposium on Theory of Computing
City	Baltimore, MD, USA
Period	5/14/90 → 5/16/90

All Science Journal Classification (ASJC) codes

General Engineering

Access to Document

10.1145/100216.100253

Cite this

@inproceedings{dbde1a48c7ff4b51ba37c9043a497618,

title = "Monotone circuits for matching require linear depth",

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

author = "Ran Raz and Avi Wigderson",

year = "1990",

doi = "10.1145/100216.100253",

language = "English (US)",

isbn = "0897913612",

series = "Proc 22nd Annu ACM Symp Theory Comput",

publisher = "Publ by ACM",

pages = "287--292",

booktitle = "Proc 22nd Annu ACM Symp Theory Comput",

note = "Proceedings of the 22nd Annual ACM Symposium on Theory of Computing ; Conference date: 14-05-1990 Through 16-05-1990",

}

TY - GEN

T1 - Monotone circuits for matching require linear depth

AU - Raz, Ran

AU - Wigderson, Avi

PY - 1990

Y1 - 1990

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

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

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

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

U2 - 10.1145/100216.100253

DO - 10.1145/100216.100253

M3 - Conference contribution

AN - SCOPUS:0025054921

SN - 0897913612

SN - 9780897913614

T3 - Proc 22nd Annu ACM Symp Theory Comput

SP - 287

EP - 292

BT - Proc 22nd Annu ACM Symp Theory Comput

PB - Publ by ACM

T2 - Proceedings of the 22nd Annual ACM Symposium on Theory of Computing

Y2 - 14 May 1990 through 16 May 1990

ER -

Monotone circuits for matching require linear depth

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this