License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.74
URN: urn:nbn:de:0030-drops-80706
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8070/
Mahajan, Meena ;
Nimbhorkar, Prajakta ;
Tawari, Anuj
Computing the Maximum using (min, +) Formulas
Abstract
We study computation by formulas over (min,+). We consider the
computation of max{x_1,...,x_n} over 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.
BibTeX - Entry
@InProceedings{mahajan_et_al:LIPIcs:2017:8070,
author = {Meena Mahajan and Prajakta Nimbhorkar and Anuj Tawari},
title = {{Computing the Maximum using (min, +) Formulas}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {74:1--74:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-046-0},
ISSN = {1868-8969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8070},
URN = {urn:nbn:de:0030-drops-80706},
doi = {10.4230/LIPIcs.MFCS.2017.74},
annote = {Keywords: Formulas, Circuits, Lower bounds, Tropical semiring}
}
|
Keywords: |
|
Formulas, Circuits, Lower bounds, Tropical semiring |
|
Collection: |
|
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.12.2017 |
