<p>Yes. We do know good lower bounds and we have known them for quite some time now.</p>

<p>Jerrum and Snir proved an <a href="http://dl.acm.org/citation.cfm?id=322341">exponential lower bound</a> over monotone arithmetic circuits for the permanent by 1980. Valiant showed even a single minus gate is <a href="http://dl.acm.org/citation.cfm?id=804412">exponentially more powerful</a>.</p>

<p>For more on (monotone) arithmetic circuits, check out Shpilka's <a href="http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf">survey</a> on arithmetic circuits.</p>

CC BY-SA 3.0
2011-11-11T02:15:45.960Z
Also worth mentioning are Shpilka's slides and video on [this page](http://intractability.princeton.edu/blog/2009/06/program-for-barriers-in-computational-complexity-workshop/).
Aaron Sterling
CC BY-SA 3.0
2011-11-11T02:02:41.357Z
2011-11-11T05:25:23.053Z
2011-11-11T05:25:23.053Z
V Vinay
<p>Another result that I'm aware of is by <a href="http://arxiv.org/abs/0907.3780">Arvind, Joglekar and Srinivasan</a> -- they present explicit polynomials computable by linear sized width-$2k$ monotone arithmetic circuits but any width-$k$ monotone arithmetic circuit would take exponential size. </p>

CC BY-SA 3.0
2011-11-11T03:20:24.520Z
2011-11-11T03:20:24.520Z
Ramprasad
<p>Does this count: Chazelle's semi-group <a href="http://www.cs.princeton.edu/~chazelle/pubs/LBOfflineRangeSearch.pdf" rel="nofollow">lower bounds</a> for fundamental range-searching problems (in the offline setting). All lower bounds are almost optimal (up to log terms when the lower bounds is polynomial and log log terms when the lower bound is polylogarithmic).</p>

CC BY-SA 3.0
2011-11-11T03:50:37.613Z
which leads me to ask if these bounds have been improved/made tight?
Sasho Nikolov
CC BY-SA 3.0
2011-11-11T03:42:40.387Z
2011-11-11T03:42:40.387Z
Sasho Nikolov
<p>Lower bounds for monotone arithmetic circuits come <strong>easier</strong> because they forbid cancellations. On the other hand, we can prove exponential lower bounds for circuits computing boolean functions even if any monotone <em>real-valued</em> functions <span class="math-container">$g:R\times R\to R$</span> are allowed as gates (see e.g. Sect. 9.6 in the <a href="https://web.vu.lt/mif/s.jukna/boolean/index.html" rel="nofollow noreferrer">book</a>).</p>
<p>Even though monotone <em>arithmetic</em> circuits are weaker than monotone <em>boolean</em> circuits (in the latter we have cancellations <span class="math-container">$a\land a=a$</span> and <span class="math-container">$a\lor (a\land b)=a$</span>), these circuits are interesting because of their relation to <strong>dynamic programming</strong> (DP) algorithms. Most of such algorithms can be simulated by circuits over semirings <span class="math-container">$(+,\min)$</span> or <span class="math-container">$(+,\max)$</span>. Gates then correspond to subproblems used by the algorithm. What Jerrum and Snir (in the paper by V Vinay) actually prove is that any DP algorithm for the Min Weight Perfect Matching (as well as for the TSP problem) must produce exponentially many subproblems. But the Perfect Mathching problem is not of &quot;DP flawor&quot; (it does not satisfy <a href="http://en.wikipedia.org/wiki/Bellman_equation#Bellman.27s_Principle_of_Optimality" rel="nofollow noreferrer">Bellman's Principle of Optimality</a>). Linear programming (not DP) is much more suited for this problem.</p>
<p>So what about optimization problems that <em>can</em> be solved by reasonably small DP algorithms - can we prove lower bounds also for them? Very interesting in this respect is an old result of Kerr (Theorem 6.1 in his <a href="https://web.vu.lt/mif/s.jukna/ftp/Kerr-phd.pdf" rel="nofollow noreferrer">phd</a>). It implies that the classical Floyd-Warshall DP algorithm for the All-Pairs Shortest Paths problem (APSP) is <em>optimal</em>: <span class="math-container">$\Omega(n^3)$</span> subproblems are necessary. Even more interesting is that Kerr's argument is very simple (much simpler than that Jerrum and Snir used): it just uses the distributivity axiom
<span class="math-container">$a+\min(b,c)=\min(a,b)+\min(a,c)$</span>, and the possibility to &quot;kill&quot; min-gates by setting one of its arguments to <span class="math-container">$0$</span>.This way he proves that <span class="math-container">$n^3$</span> plus-gates are necessary to multiply two <span class="math-container">$n\times n$</span> matrices over the semiring <span class="math-container">$(+,\min)$</span>. In Sect. 5.9 of the <a href="http://books.google.com/books?id=SJJQAAAAMAAJ&amp;q=Aho+Hopcroft+Ullman+The+Design+and+Analysis&amp;dq=Aho+Hopcroft+Ullman+The+Design+and+Analysis&amp;hl=de&amp;ei=4v28TvanJMO6hAe7suWXBA&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CC0Q6AEwAA" rel="nofollow noreferrer">book</a> by Aho, Hopcroft and Ullman it is shown that this problem is equivalent to APSP problem.</p>
<p>A next question could be: what about the Single-Source Shortest Paths (SSSP) problem? Bellman-Ford DP algorithm for this (seemingly &quot;simpler&quot;) problem also uses <span class="math-container">$O(n^3)$</span> gates. Is this optimal? So far, no separation between these two versions of the shortest path problem are known; see an interesting <a href="http://www.stanford.edu/%7Errwill/tria-mmult.pdf" rel="nofollow noreferrer">paper</a> of Virginia and Ryan Williams along these lines. So, an <span class="math-container">$\Omega(n^3)$</span> lower bound in <span class="math-container">$(+,\min)$</span>-circuits for SSSP would be a great result. Next question could be: what about lower bounds for Knapsack?  In this <a href="https://web.vu.lt/mif/s.jukna/ftp/incremental3.pdf" rel="nofollow noreferrer">draft</a> lower bounds for Knapsack are proved in weaker model of <span class="math-container">$(+,\max)$</span> circuits where the usage of <span class="math-container">$+$</span>-gates is restricted; in Appendix Kerr's proof is reproduced.</p>

CC BY-SA 4.0
2011-11-11T11:18:29.613Z
2021-12-16T10:32:52.080Z
2021-12-16T10:32:52.080Z
Stasys
<p>The state of our knowledge about <a href="http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Lower_bounds" rel="nofollow noreferrer">general arithmetic circuits</a> seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have exponential size lower-bounds for <a href="http://en.wikipedia.org/wiki/Monotone_circuit#History" rel="nofollow noreferrer">monotone Boolean circuits</a>. </p>

<blockquote>
  <p>What do we know about <em>monotone</em> arithmetic circuits? 
  Do we have similar good lower-bounds for them? 
  If not, what is the essential difference that doesn't allow us to get similar lower-bounds for monotone arithmetic circuits?</p>
</blockquote>

<p>The question is inspired by comments on <a href="https://cstheory.stackexchange.com/q/8853/186">this question</a>.</p>

CC BY-SA 3.0
2011-11-11T20:02:02.917Z
I was trying to get a better understanding of the difference between arithmetic circuits and Boolean circuits and reading your answers helped me in attaining a better understanding. Thanks a lot for interesting answers (and questions).
Kaveh
<cc.complexity-theory><circuit-complexity><boolean-functions><monotone><arithmetic-circuits>
Monotone arithmetic circuits
Kaveh
# Monotone arithmetic circuits

(Asked by: username_0 on 2011-11-10)

The state of our knowledge about [general arithmetic circuits](http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Lower_bounds) seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have exponential size lower-bounds for [monotone Boolean circuits](http://en.wikipedia.org/wiki/Monotone_circuit#History).

> What do we know about *monotone* arithmetic circuits?
> Do we have similar good lower-bounds for them?
> If not, what is the essential difference that doesn't allow us to get similar lower-bounds for monotone arithmetic circuits?

The question is inspired by comments on [this question](https://cstheory.stackexchange.com/q/8853/186).

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions, monotone, arithmetic-circuits

> **Comments:**
> **username_0**: I was trying to get a better understanding of the difference between arithmetic circuits and Boolean circuits and reading your answers helped me in attaining a better understanding. Thanks a lot for interesting answers (and questions).  

---

## 4 answers

### Answer by username_5 on 2011-11-11. Score: 25 | Accepted answer

Lower bounds for monotone arithmetic circuits come **easier** because they forbid cancellations. On the other hand, we can prove exponential lower bounds for circuits computing boolean functions even if any monotone *real-valued* functions $g:R\times R\to R$ are allowed as gates (see e.g. Sect. 9.6 in the [book](https://web.vu.lt/mif/s.jukna/boolean/index.html)).

Even though monotone *arithmetic* circuits are weaker than monotone *boolean* circuits (in the latter we have cancellations $a\land a=a$ and $a\lor (a\land b)=a$), these circuits are interesting because of their relation to **dynamic programming** (DP) algorithms. Most of such algorithms can be simulated by circuits over semirings $(+,\min)$ or $(+,\max)$. Gates then correspond to subproblems used by the algorithm. What Jerrum and Snir (in the paper by username_1) actually prove is that any DP algorithm for the Min Weight Perfect Matching (as well as for the TSP problem) must produce exponentially many subproblems. But the Perfect Mathching problem is not of "DP flawor" (it does not satisfy [Bellman's Principle of Optimality](http://en.wikipedia.org/wiki/Bellman_equation#Bellman.27s_Principle_of_Optimality)). Linear programming (not DP) is much more suited for this problem.

So what about optimization problems that *can* be solved by reasonably small DP algorithms - can we prove lower bounds also for them? Very interesting in this respect is an old result of Kerr (Theorem 6.1 in his [phd](https://web.vu.lt/mif/s.jukna/ftp/Kerr-phd.pdf)). It implies that the classical Floyd-Warshall DP algorithm for the All-Pairs Shortest Paths problem (APSP) is *optimal*: $\Omega(n^3)$ subproblems are necessary. Even more interesting is that Kerr's argument is very simple (much simpler than that Jerrum and Snir used): it just uses the distributivity axiom
$a+\min(b,c)=\min(a,b)+\min(a,c)$, and the possibility to "kill" min-gates by setting one of its arguments to $0$.This way he proves that $n^3$ plus-gates are necessary to multiply two $n\times n$ matrices over the semiring $(+,\min)$. In Sect. 5.9 of the [book](http://books.google.com/books?id=SJJQAAAAMAAJ&q=Aho+Hopcroft+Ullman+The+Design+and+Analysis&dq=Aho+Hopcroft+Ullman+The+Design+and+Analysis&hl=de&ei=4v28TvanJMO6hAe7suWXBA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CC0Q6AEwAA) by Aho, Hopcroft and Ullman it is shown that this problem is equivalent to APSP problem.

A next question could be: what about the Single-Source Shortest Paths (SSSP) problem? Bellman-Ford DP algorithm for this (seemingly "simpler") problem also uses $O(n^3)$ gates. Is this optimal? So far, no separation between these two versions of the shortest path problem are known; see an interesting [paper](http://www.stanford.edu/%7Errwill/tria-mmult.pdf) of Virginia and Ryan Williams along these lines. So, an $\Omega(n^3)$ lower bound in $(+,\min)$-circuits for SSSP would be a great result. Next question could be: what about lower bounds for Knapsack? In this [draft](https://web.vu.lt/mif/s.jukna/ftp/incremental3.pdf) lower bounds for Knapsack are proved in weaker model of $(+,\max)$ circuits where the usage of $+$-gates is restricted; in Appendix Kerr's proof is reproduced.


---

### Answer by username_1 on 2011-11-11. Score: 15

Yes. We do know good lower bounds and we have known them for quite some time now.

Jerrum and Snir proved an [exponential lower bound](http://dl.acm.org/citation.cfm?id=322341) over monotone arithmetic circuits for the permanent by 1980. Valiant showed even a single minus gate is [exponentially more powerful](http://dl.acm.org/citation.cfm?id=804412).

For more on (monotone) arithmetic circuits, check out Shpilka's [survey](http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf) on arithmetic circuits.

> **Comments:**
> **username_2**: Also worth mentioning are Shpilka's slides and video on [this page](http://intractability.princeton.edu/blog/2009/06/program-for-barriers-in-computational-complexity-workshop/).  

---

### Answer by username_3 on 2011-11-11. Score: 6

Another result that I'm aware of is by [Arvind, Joglekar and Srinivasan](http://arxiv.org/abs/0907.3780) -- they present explicit polynomials computable by linear sized width-$2k$ monotone arithmetic circuits but any width-$k$ monotone arithmetic circuit would take exponential size.


---

### Answer by username_4 on 2011-11-11. Score: 3

Does this count: Chazelle's semi-group [lower bounds](http://www.cs.princeton.edu/~chazelle/pubs/LBOfflineRangeSearch.pdf) for fundamental range-searching problems (in the offline setting). All lower bounds are almost optimal (up to log terms when the lower bounds is polynomial and log log terms when the lower bound is polylogarithmic).

> **Comments:**
> **username_4**: which leads me to ask if these bounds have been improved/made tight?  

---

