Monotone Circuit Complexity of Matching

by Bruno Pasqualotto Cavalar, Mika Goos, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov

Oded's comments

Again, I will let the abstract talk for itself.

Original abstract

We show that the perfect matching function on $n$-vertex graphs requires monotone circuits of size $\smash{2^{n^{\Omega(1)}}}$. 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.

See ECCC TR25-102.

Back to list of Oded's choices.