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

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

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