ECCC-Report TR18-020https://eccc.weizmann.ac.il/report/2018/020Comments and Revisions published for TR18-020en-usTue, 27 Mar 2018 10:52:28 +0300
Comment 1
| (Min, Plus) is Not stronger than (Or, And) |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2018/020#comment1We observe that a known structural property of (min,+) circuits (and formulas) implies that lower bounds on the monotone circuit/formula size remain valid also for (min,+) circuits, even when only nonnegative integer weights are allowed. So, the lower bound proved in ECCC TR18-020 can be alternatively derived from known lower bounds on the monotone formula complexity of the threshold-2 function.Tue, 27 Mar 2018 10:52:28 +0300https://eccc.weizmann.ac.il/report/2018/020#comment1
Paper TR18-020
| Computing the maximum using $(\min, +)$ formulas |
Meena Mahajan,
Prajakta Nimbhorkar,
Anuj Tawari
https://eccc.weizmann.ac.il/report/2018/020We 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.Tue, 30 Jan 2018 08:56:35 +0200https://eccc.weizmann.ac.il/report/2018/020