Name
Abstract | ||
|---|---|---|
We study computation by formulas over (min,+). We consider thecomputation of max{x_1,...,x_n} over N as a difference of(min,+) formulas, and show that size n + n log n is sufficientand necessary. Our proof also shows that any (min,+) formulacomputing the minimum of all sums of n-1 out of n variables musthave n log n leaves; this too is tight. Our proofs use acomplexity measure for (min,+) functions based on minterm-likebehaviour and on the entropy of an associated graph. |
Year | Venue | DocType |
|---|---|---|
2018 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
25 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| Prajakta Nimbhorkar | 2 | 170 | 15.04 |
| Anuj Tawari | 3 | 0 | 1.01 |