Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with tropical semiring:
TR18-020 | 30th January 2018
Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

Computing the maximum using $(\min, +)$ formulas

Comments: 1

We study computation by formulas over $(min, +)$. We consider the computation of $\max\{x_1,\ldots,x_n\}$
over $\mathbb{N}$ as a difference of $(\min, +)$ formulas, and show that size $n + n \log n$ is sufficient and necessary. Our proof also shows that any $(\min, +)$ formula computing the minimum of all ... more >>>

TR18-146 | 18th August 2018
Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

Shortest path length with bounded-alternation $(\min, +)$ formulas

We study bounded depth $(\min, +)$ formulas computing the shortest path polynomial. For depth $2d$ with $d \geq 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 ... more >>>

ISSN 1433-8092 | Imprint