<p><a href="http://link.springer.com/chapter/10.1007/3-540-10003-2_103">Snir</a> 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). </p>

<p>The <a href="http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf">survey</a> 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 <a href="http://dl.acm.org/citation.cfm?id=322341">Jerrum and Snir</a>)</p>

CC BY-SA 3.0
2014-02-25T17:18:40.150Z
2014-02-25T17:18:40.150Z
Sasho Nikolov
<p>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? </p>

CC BY-SA 3.0
2014-02-25T17:44:16.813Z
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: http://dx.doi.org/10.1145/800135.804412
Joshua Grochow
<cc.complexity-theory><algebraic-complexity><permanent><formulas>
Size of Formulas with no negative sign for Matrix Permanent
Turbo
# Size of Formulas with no negative sign for Matrix Permanent

(Asked by: username_0 on 2014-02-25)

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?

**Tags:** cc.complexity-theory, algebraic-complexity, permanent, formulas
> **Comments:**
> **username_1**: 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: http://dx.doi.org/10.1145/800135.804412  

---

## 1 answers

### Answer by username_2 on 2014-02-25. Score: 6 | Accepted answer

[Snir](http://link.springer.com/chapter/10.1007/3-540-10003-2_103) 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](http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf) 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](http://dl.acm.org/citation.cfm?id=322341))


---

