Document Open Access Logo

Computing the Maximum using (min, +) Formulas

Authors Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.74.pdf
  • Filesize: 391 kB
  • 11 pages

Document Identifiers

Author Details

Meena Mahajan
Prajakta Nimbhorkar
Anuj Tawari

Cite As Get BibTex

Meena Mahajan, Prajakta Nimbhorkar, and Anuj Tawari. Computing the Maximum using (min, +) Formulas. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 74:1-74:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.74

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.

Subject Classification

Keywords
  • Formulas
  • Circuits
  • Lower bounds
  • Tropical semiring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Eric Allender. Arithmetic circuits and counting complexity classes. In Jan Krajicek, editor, Complexity of Computations and Proofs, Quaderni di Matematica Vol. 13, pages 33-72. Seconda Universita di Napoli, 2004. An earlier version appeared in the Complexity Theory Column, SIGACT News 28, 4 (Dec. 1997) pp. 2-15. Google Scholar
  2. Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, 16:87-90, 1956. Google Scholar
  3. Imre Csiszár, János Körner, László Lovász, Katalin Marton, and Gábor Simonyi. Entropy splitting for antiblocking corners and perfect graphs. Combinatorica, 10(1):27-40, 1990. Google Scholar
  4. Robert W Floyd. Algorithm 97: shortest path. Communications of the ACM, 5(6):345, 1962. Google Scholar
  5. Lester R Ford Jr. Network flow theory. Technical Report P-923, Rand Corporation, 1956. Google Scholar
  6. Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1):196-210, 1962. Google Scholar
  7. Mark Jerrum and Marc Snir. Some exact complexity results for straight-line computations over semirings. Journal of the ACM (JACM), 29(3):874-897, 1982. Google Scholar
  8. Stasys Jukna. Lower bounds for tropical circuits and dynamic programs. Theory of Computing Systems, 57(1):160-194, 2015. Google Scholar
  9. Stasys Jukna. Tropical complexity, Sidon sets, and dynamic programming. SIAM Journal on Discrete Mathematics, 30(4):2064-2085, 2016. Google Scholar
  10. Stasys Jukna and Georg Schnitger. On the optimality of Bellman-Ford-Moore shortest path algorithm. Theoretical Computer Science, 628:101-109, 2016. Google Scholar
  11. János Körner. Coding of an information source having ambiguous alphabet and the entropy of graphs. In Transactions of 6th Prague Conference on Information Theory, pages 411-425. Academia, Prague, 1973. Google Scholar
  12. János Körner. Fredman-Komlós bounds and information theory. SIAM. J. on Algebraic and Discrete Methods, 7(4):560-570, 1986. Google Scholar
  13. János Körner and Katalin Marton. New bounds for perfect hashing via information theory. European Journal of Combinatorics, 9(6):523-530, 1988. Google Scholar
  14. Edward F Moore. The shortest path through a maze. Bell Telephone System., 1959. Google Scholar
  15. Ilan Newman and Avi Wigderson. Lower bounds on formula size of boolean functions using hypergraph entropy. SIAM Journal on Discrete Mathematics, 8(4):536-542, 1995. Google Scholar
  16. Gábor Simonyi. Graph entropy: A survey. Combinatorial Optimization, 20:399-441, 1995. Google Scholar
  17. Gábor Simonyi. Perfect graphs and graph entropy: An updated survey. In Perfect Graphs, pages 293-328. John Wiley and Sons, 2001. Google Scholar
  18. Stephen Warshall. A theorem on Boolean matrices. Journal of the ACM (JACM), 9(1):11-12, 1962. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact