Alladi Ramakrishnan Hall

Computing max using (min,+) formulas

Anuj Tawari

IMSc

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.