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?

  • 4
    $\begingroup$ 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 $\endgroup$ Feb 25 '14 at 17:44

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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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