<p>Eva Tardos proved that the gap is truly exponential by showing that there is a monotone boolean function that has poly size circuits but requires exponential size monotone circuits. Nothing better than super-polynomial is known for matching.</p>

<p>Raz has a result that monotone circuits for matching have linear depth. (Thanks Klauck, for pointing the typo.) </p>

<p>AFAIK, we know nothing better.</p>

<p>Ref: (1) <a href="http://www.springerlink.com/index/P25X5838624J0352.pdf">http://www.springerlink.com/index/P25X5838624J0352.pdf</a></p>

<p>(2) <a href="http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmatching.ps">http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmatching.ps</a></p>

CC BY-SA 2.5
2011-01-11T17:52:41.207Z
Come on, it's linear depth (and its Raz and Wigderson).
Hartmut Klauck
CC BY-SA 3.0
2011-07-09T19:56:33.870Z
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
CC BY-SA 2.5
2011-01-11T10:20:45.043Z
2011-01-12T16:01:15.660Z
2011-01-12T16:01:15.660Z
V Vinay
<p>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.</p>

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

<cc.complexity-theory><circuit-complexity><matching>
Improved lower bound on monotone circuit complexity of perfect matching?
slimton
# Improved lower bound on monotone circuit complexity of perfect matching?

(Asked by: username_0 on 2011-01-11)

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.

**Tags:** cc.complexity-theory, circuit-complexity, matching


---

## 1 answers

### Answer by username_1 on 2011-01-11. Score: 11

Eva Tardos proved that the gap is truly exponential by showing that there is a monotone boolean function that has poly size circuits but requires exponential size monotone circuits. Nothing better than super-polynomial is known for matching.

Raz has a result that monotone circuits for matching have linear depth. (Thanks Klauck, for pointing the typo.)

AFAIK, we know nothing better.

Ref: (1) <http://www.springerlink.com/index/P25X5838624J0352.pdf>

(2) <http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmatching.ps>

> **Comments:**
> **username_2**: Come on, it's linear depth (and its Raz and Wigderson).  
> **username_3**: 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.  

---

