| Autor: |
Mahajan, Meena, Nimbhorkar, Prajakta, Tawari, Anuj |
| Zdroj: |
International Journal of Advances in Engineering Sciences & Applied Mathematics; Mar2019, Vol. 11 Issue 1, p68-74, 7p |
| Abstrakt: |
We study bounded-depth (min , +) formulas computing the shortest path polynomial. For depth 2d with d ≥ 2 , we obtain lower bounds parameterized by certain fan-in restrictions on + gates except those at the bottom level. For depth 4, in two regimes of the parameter, the bounds are tight. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Full text from SpringerLink