Monotone Circuit Complexity of Matching

Key Points

• Perfect matching function requires monotone circuits of size 2^{n^{Ω(1)}}, significantly improving previous bounds.
• Previous lower bound of n^{Ω(log n)} set by Razborov in 1985 is surpassed by current findings.
• The proof employs a standard approximation method combined with a novel sunflower lemma for matchings.
• Implications suggest that matching problems are more complex than previously understood, calling for deeper analysis.