文章基本信息
- 标题：Shortest path length with bounded-alternation ( min + ) formulas
- 本地全文：下载
- 作者：Meena Mahajan ; Prajakta Nimbhorkar ; Anuj Tawari 等
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2018
- 卷号：2018
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
We study bounded depth ( min + ) formulas computing the shortest path polynomial. For depth 2 d with d 2 , we obtain lower bounds parametrized by certain fan-in restrictions on all + gates except those at the bottom level. For depth 4 , in two regimes of the parameter, the bounds are tight.
- 关键词：circuits ; formulas ; lower bounds ; shortest path ; tropical semiring
