Monotone Circuit Complexity of Matching
We show that the perfect matching function on n-vertex graphs requires monotone circuits of size 2nΩ(1). This improves on the nΩ(logn) lower bound of Razborov (1985). Our proof uses the standard approximation method together with a new sunflower lemma for matchings.
Authors
- Bruno Pasqualotto Cavalar (ORCID: https://orcid.org/0000-0002-0458-8767)
- Artur Riazanov (ORCID: https://orcid.org/0000-0001-7892-1502)
- Anastasia Sofronova
- Dmitry Sokolov (ORCID: https://orcid.org/0000-0003-2809-3467)
- Mika Göös
Institutions
- University of Oxford (GB)
- École Polytechnique Fédérale de Lausanne (CH)
- Université de Montréal (CA)
Publication Details
- Published
- 2026-06-09
- DOI
- https://doi.org/10.1145/3798129.3800824
- Citations
- 1
- Primary Topic
- Machine Learning and Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 19.56
Funders
- Royal Society