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

month = jan,

day = "1",

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

}