Monotone arithmetic circuits The state of our knowledge about general arithmetic circuits 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. 


  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.
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).

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 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 "DP flawor" (it does not satisfy Bellman's 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). 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 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 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 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.