12
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Come on, it's linear depth (and its Raz and Wigderson). $\endgroup$
    – Hartmut Klauck
    Jan 11, 2011 at 17:52
  • 4
    $\begingroup$ 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. $\endgroup$
    – Stasys
    Jul 9, 2011 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.