Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

What is the best lower bound for algebraic formulas for Permanent of a matrix given that the formulas have no negative sign? Is there an exponential lower bound known for such formulas and what would be a good reference on the topic?

share|improve this question
4  
You might also be interested to know that Valiant proved there are polynomials where there is an exponential gap between their monotone and non-monotone algebraic circuit complexities (in particular, the perfect matching polynomial for a certain family of graphs). See: dx.doi.org/10.1145/800135.804412 –  Joshua Grochow Feb 25 at 17:44
add comment

1 Answer 1

up vote 6 down vote accepted

Snir has proved a tight lower bound on the size of monotone formulas representing the permanent of an $n\times n$ matrix. The lower bound is $2^{2n - 0.25\log^2 n}$, and he notes that a formula of size $2^{2n - 0.25\log^2 n + O(\log n)}$ exists (Theorem 3.1. and comment after the proof).

The survey by Shpilka, and Yehudayoff is a good resource. Also, a lower bound of $2^{\Omega(n)}$ on the size of monotone circuits for the permanent is known as well (proved by Jerrum and Snir)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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