Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-080 | 29th July 2014 12:44

Lower Bounds for Tropical Circuits and Dynamic Programs

RSS-Feed




Revision #1
Authors: Stasys Jukna
Accepted on: 29th July 2014 12:44
Downloads: 6405
Keywords: 


Abstract:

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower bounds arguments for tropical circuits, and hence, for dynamic programs.



Changes to previous version:

(1) Corrected reduction to arithmetic circuits (it holds only for multilinear polynomials, see Sect. 4), (2) added lower bounds for the depth of tropical circuits (Sect. 15), (3) give simple solution of Open Problem 3 about Min/Max gaps (Lemma 10), (4) corrected other small errors.


Paper:

TR14-080 | 11th June 2014 23:09

Lower Bounds for Tropical Circuits and Dynamic Programs





TR14-080
Authors: Stasys Jukna
Publication: 11th June 2014 23:09
Downloads: 966
Keywords: 


Abstract:

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower bounds arguments for tropical circuits, and hence, for dynamic programs.



ISSN 1433-8092 | Imprint