University of Cambridge > Talks.cam > Algorithms and Complexity Seminar > Monotone Circuit Complexity of Matching

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Monotone Circuit Complexity of Matching

Download to your calendar using vCal

If you have a question about this talk, please contact Tom Gur .

We show that the perfect matching function on $n$-vertex graphs requires monotone circuits of size $2}$. This improves on the $n{\Omega(\log n)}$ lower bound of Razborov (1985). Our proof uses the standard approximation method together with a new sunflower lemma for matchings.

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Cambridge University Department of Social Anthropology - ROOM 2.3 bdj50: Conference on the past, present and future of Josephson Physics BCNI seminar room, Sir William Hardy Building, Downing Site

Other talks

Spectral rigidity of random covers of compact hyperbolic surfaces Packing the Border: Quail Crates and the Regulation of Animal Movement on the US-Mexico Border, 1910s-1940s BSU Seminar: "Response Adaptivity Across Clinical Trials In Portfolios of Biomedical Innovations" Optimal metric and approximation of free boundary minimal surfaces Semiconductor-based neutron detector development at QMUL Title to be confirmed
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity