Lower Bounds for Tropical Circuits and Dynamic Programs

被引：0
作者：
Stasys Jukna
机构：
[1] University of Frankfurt,Institute of Computer Science
[2] Vilnius University,Institute of Mathematics and Informatics
来源：
Theory of Computing Systems | 2015年 / 57卷
关键词：
Tropical circuits; Dynamic programming; Monotone arithmetic circuits; Lower bounds;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：160 / 194
页数：34
相关论文
共 55 条
[1]  
Alon N(1987)The monotone circuit complexity of boolean functions Combinatorica 7 1-22
[2]  
Boppana R(1989)Explicit constructions of linear sized tolerant networks Discrete Math. 72 15-19
[3]  
Alon N(1985)On a method for obtaining lower bounds for the complexity of individual monotone functions Soviet Math. Dokl. 31 530-534
[4]  
Chung FRK(1987)A method for obtaining efficient lower bounds for monotone complexity Algebra and Logics 26 1-18
[5]  
Andreev AE(1983)The complexity of partial derivatives Theoret. Comput. Sci. 22 317-330
[6]  
Andreev AE(1958)On a routing problem Quarterly of Appl. Math. 16 87-90
[7]  
Baur W(1962)Algorithm 97, shortest path Comm. ACM 5 345-13
[8]  
Strassen V(1987)On one method of obtaining lower bounds on the monotone complexity of polynomials Vestnik MGU, Series 1 Mathematics, Mechanics 5 7-350
[9]  
Bellman R(2005)On the complexity of calculation of differentials and gradients Discrete Math. Appl. 15 327-70
[10]  
Floyd RW(2012)A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials Math. Sbornik 203 33-1294
123456