Monotone Circuit Complexity of Matching

Bruno Cavalar; Mika Göös; Artur Riazanov; Anastasia Sofronova; Dmitry Sokolov

doi:10.1145/3798129.3800824

STOC2026顶会

Monotone Circuit Complexity of Matching

Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

arXiv DOI 出版方

2026年份

7被引次数

4顶会引用

摘要

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