Monotone Circuit Complexity of Matching

Proceedings of the 58th Annual ACM Symposium on Theory of Computing 2026 Open access

Read full text
Authors: Bruno Pasqualotto Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
DOI: 10.1145/3798129.3800824
Cited by: 1
References: 42

Abstract

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.

Fields of Study & Subjects

Machine Learning and Algorithms VLSI and Analog Circuit Testing DNA and Biological Computing

Publication details

Journal / source
Proceedings of the 58th Annual ACM Symposium on Theory of Computing
Publisher
ACM
Pages
1128–1132
Publication date
9 June 2026
Language
EN