2026-07-26T01:16:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8070 2024-03-06T10:40:59Z ddc:004 open_access

Computing the Maximum using (min, +) Formulas Mahajan, Meena Nimbhorkar, Prajakta Tawari, Anuj Formulas Circuits Lower bounds Tropical semiring 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Meena Mahajan and Prajakta Nimbhorkar and Anuj Tawari 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.74 urn:nbn:de:0030-drops-80706 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.74 eng https://creativecommons.org/licenses/by/3.0/legalcode