Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TROPICAL CIRCUITS:
Reports tagged with tropical circuits:
TR14-080 | 11th June 2014
Stasys Jukna

#### Lower Bounds for Tropical Circuits and Dynamic Programs

Revisions: 1

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower ... more >>>

TR18-049 | 14th March 2018
Stasys Jukna, Hannes Seiwert

#### Greedy can also beat pure dynamic programming

Revisions: 1

Many dynamic programming algorithms are pure'' in that they only use min or max and addition operations in their recursion equations. The well known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on $n$-vertex graphs using only $O(n^2\log n)$ operations. We prove that any pure DP algorithm ... more >>>

TR18-051 | 15th March 2018
Stasys Jukna

#### Derandomizing Dynamic Programming and Beyond

Revisions: 1

We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description complexity as gates. We show that such circuits can be simulated by deterministic circuits with an only polynomial blowup in size. An algorithmic consequence is that randomization cannot substantially speed up dynamic programming. ... more >>>

TR18-127 | 9th July 2018
Stasys Jukna, Hannes Seiwert

#### Approximation Limitations of Tropical Circuits

We develop general lower bound arguments for approximating tropical
(min,+) and (max,+) circuits, and use them to prove the
first non-trivial, even super-polynomial, lower bounds on the size
of such circuits approximating some explicit optimization
problems. In particular, these bounds show that the approximation
powers of pure dynamic programming algorithms ... more >>>

TR20-178 | 30th November 2020
Stasys Jukna, Hannes Seiwert, Igor Sergeev

#### Reciprocal Inputs in Arithmetic and Tropical Circuits

It is known that the size of monotone arithmetic $(+,\ast)$ circuits can be exponentially decreased by allowing just one division "at the very end," at the output gate. A natural question is: can the size of $(+,\ast)$ circuits be substantially reduced if we allow divisions "at the very beginning," that ... more >>>

TR22-094 | 3rd July 2022
Stasys Jukna

#### Notes on Monotone Read-k Circuits

Revisions: 1

A monotone Boolean $(\lor,\land)$ circuit $F$ computing a Boolean function $f$ is a read-$k$ circuit if the polynomial produced (purely syntactically) by the arithmetic $(+,\times)$ version of $F$ has the property that for every prime implicant of $f$, the polynomial contains a monomial with the same set of variables, each ... more >>>

ISSN 1433-8092 | Imprint