# Improved lower bound on monotone circuit complexity of perfect matching?

Razborov proved that every monotone circuit that computes the perfect matching function for bipartite graphs must have at least $n^{\Omega(\log n)}$ gates (he called it "logical permanent"). Has a better lower bound for the same problem been proved since then? (say $2^{n^\epsilon}$?) As far as I remember this problem was open in the mid 1990's.

I am aware that the clique function requires exponential-size monotone circuits and so on, but I am interested in perfect matching specifically.

• Come on, Hartmut, the depth lower bound is only $N^{1/2}$ where $N$ is the number of variables (=edges). So far we do not have any $\Omega(N)$ depth lower bound, even for monotone circuits. The Perfect Matching is another story. None of "refined" lower bound arguments can beat Razborov's lower bound $N^{\Omega(\log N)}$ on the size. – Stasys Jul 9 '11 at 19:56