Monotone circuit complexity of matching

Bruno Pasqualotto Cavalar ( University of Oxford )

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