Name
Abstract | ||
|---|---|---|
We study bounded-depth \((\min ,+)\) formulas computing the shortest path polynomial. For depth 2d with \(d \ge 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.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s12572-018-0229-6 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
Formulas, Circuits, Lower bounds, Tropical semiring, Shortest path | Discrete mathematics,Parameterized complexity,Polynomial,Shortest path problem,Classical mechanics,Mathematics,Alternation (linguistics),Bounded function | Journal |
Volume | Issue | ISSN |
25 | 1 | 0975-5616 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| Prajakta Nimbhorkar | 2 | 170 | 15.04 |
| Anuj Tawari | 3 | 0 | 1.01 |