Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-129 | 30th July 2026 02:11

Monotone circuit lower bounds from spread matchings

RSS-Feed




TR26-129
Authors: Anup Rao
Publication: 30th July 2026 02:11
Downloads: 82
Keywords: 


Abstract:

We prove new exponential monotone circuit lower bounds for detecting perfect matchings. We show that $\exp(\widetilde{\Omega}(n^{1/2}))$ gates are required to detect bipartite perfect matchings in $n$-vertex graphs. Our lower bounds are based on a new spread matching lemma.



ISSN 1433-8092 | Imprint