Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-020 | 30th January 2018 08:33

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

RSS-Feed




TR18-020
Authors: Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari
Publication: 30th January 2018 08:56
Downloads: 149
Keywords: 


Abstract:

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 sums of $n - 1$ out of $n$ variables must have $n \log n$ leaves; this too is tight. Our proofs use a
complexity measure for $(\min, +)$ functions based on minterm-like behaviour and on the entropy of an
associated graph.



ISSN 1433-8092 | Imprint