Monotone Circuit Complexity of Matching

Add to your list(s) Download to your calendar using vCal

• Bruno Cavalar (Oxford)
• Tuesday 07 October 2025, 10:00-11:00
• Computer Laboratory, William Gates Building, Room SS03.

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:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk449

Note that ex-directory lists are not shown.