22
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Kaveh Nov 11 '11 at 20:02
25
$\begingroup$

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.

$\endgroup$
15
$\begingroup$

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 over monotone arithmetic circuits for the permanent by 1980. Valiant showed even a single minus gate is exponentially more powerful.

For more on (monotone) arithmetic circuits, check out Shpilka's survey on arithmetic circuits.

$\endgroup$
  • 3
    $\begingroup$ Also worth mentioning are Shpilka's slides and video on this page. $\endgroup$ – Aaron Sterling Nov 11 '11 at 2:15
6
$\begingroup$

Another result that I'm aware of is by Arvind, Joglekar and Srinivasan -- they present explicit polynomials computable by linear sized width-$2k$ monotone arithmetic circuits but any width-$k$ monotone arithmetic circuit would take exponential size.

$\endgroup$
3
$\begingroup$

Does this count: Chazelle's semi-group lower bounds 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).

$\endgroup$
  • 2
    $\begingroup$ which leads me to ask if these bounds have been improved/made tight? $\endgroup$ – Sasho Nikolov Nov 11 '11 at 3:50

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.