# Size of Formulas with no negative sign for Matrix Permanent

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?

• 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 '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)