### 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 | |

State | Published - Jan 1 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

- Engineering(all)

## Fingerprint Dive into the research topics of 'Monotone circuits for matching require linear depth'. Together they form a unique fingerprint.

## Cite this

Raz, R., & Wigderson, A. (1990). Monotone circuits for matching require linear depth. In

*Proc 22nd Annu ACM Symp Theory Comput*(pp. 287-292). (Proc 22nd Annu ACM Symp Theory Comput). Publ by ACM. https://doi.org/10.1145/100216.100253