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