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 >>>

TR24-072 | 11th April 2024
Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch

Tropical proof systems

Propositional proof complexity deals with the lengths of polynomial-time verifiable proofs for Boolean tautologies. An abundance of proof systems is known, including algebraic and semialgebraic systems, which work with polynomial equations and inequalities, respectively. The most basic algebraic proof system is based on Hilbert's Nullstellensatz (Beame et al., 1996). Tropical ... more >>>

ISSN 1433-8092 | Imprint