Document Open Access Logo

On Problems Equivalent to (min,+)-Convolution

Authors Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.22.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Marek Cygan
Marcin Mucha
Karol Wegrzycki
Michal Wlodarczyk

Cite As Get BibTex

Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On Problems Equivalent to (min,+)-Convolution. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.22

Abstract

In the recent years, significant progress has been made in explaining apparent hardness of improving over naive solutions for many fundamental polynomially solvable problems. This came in the form of conditional lower bounds -- reductions from a problem assumed to be hard.  These include 3SUM, All-Pairs Shortest Paths, SAT and Orthogonal Vectors, and others. 

In the (min,+)-convolution problem, the goal is to compute a sequence c, where c[k] = min_i a[i]+b[k-i], given sequences a and b. This can easily be done in O(n^2) time, but no O(n^{2-eps}) algorithm is known for eps > 0. In this paper we undertake a systematic study of the (min,+)-convolution problem as a hardness assumption. 

As the first step, we establish equivalence of this problem to a group of other problems, including variants of the classic knapsack problem and problems related to subadditive sequences. The (min,+)-convolution has been used as a building block in algorithms for many problems, notably problems in stringology. It has also already appeared as an ad hoc hardness assumption. We investigate some of these connections and provide new reductions and other results.

Subject Classification

Keywords
  • fine-grained complexity
  • knapsack
  • conditional lower bounds
  • (min,+)-convolution
  • subquadratic equivalence

Metrics

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

References

  1. Amir Abboud. Personal communication. Google Scholar
  2. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 59-78. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.14.
  3. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 51-58. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746612.
  4. Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. Better approximations for tree sparsity in nearly-linear time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2215-2229. SIAM, 2017. Google Scholar
  5. Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. Subquadratic Algorithms for 3SUM. In Proceedings of the 9th International Conference on Algorithms and Data Structures, WADS'05, pages 409-421, Berlin, Heidelberg, 2005. Springer-Verlag. URL: http://dx.doi.org/10.1007/11534273_36.
  6. Richard Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, USA, 1957. Google Scholar
  7. David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian. Necklaces, Convolutions, and X + Y. In Yossi Azar and Thomas Erlebach, editors, Algorithms - ESA 2006: 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006. Proceedings, pages 160-171, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  8. Karl Bringmann. A near-linear pseudopolynomial time algorithm for subset sum. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1073-1084. SIAM, 2017. Google Scholar
  9. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 79-97. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.15.
  10. Peter Burcsi, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. On table arrangements, scrabble freaks, and jumbled pattern matching. In Paolo Boldi and Luisa Gargano, editors, Fun with Algorithms, 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings, volume 6099 of Lecture Notes in Computer Science, pages 89-101. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-13122-6_11.
  11. Peter Burcsi, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. On approximate jumbled pattern matching in strings. Theory Comput. Syst., 50(1):35-51, 2012. URL: http://dx.doi.org/10.1007/s00224-011-9344-5.
  12. Michael R. Bussieck, Hannes Hassler, Gerhard J. Woeginger, and Uwe T. Zimmermann. Fast algorithms for the maximum convolution problem. Oper. Res. Lett., 15(3):133-141, 1994. URL: http://dx.doi.org/10.1016/0167-6377(94)90048-5.
  13. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 261-270. ACM, 2016. URL: http://dx.doi.org/10.1145/2840728.2840746.
  14. Coralia Cartis and Andrew Thompson. An exact tree projection algorithm for wavelets. IEEE Signal Processing Letters, 20(11):1026-1029, 2013. Google Scholar
  15. Timothy M. Chan and Moshe Lewenstein. Clustered Integer 3SUM via Additive Combinatorics. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC'15, pages 31-40, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2746539.2746568.
  16. Ferdinando Cicalese, Eduardo Sany Laber, Oren Weimann, and Raphael Yuster. Approximating the maximum consecutive subsums of a sequence. Theor. Comput. Sci., 525:130-137, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2013.05.032.
  17. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dańiel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlstrom. On problems as hard as cnf-sat. In Proceedings of the 2012 IEEE Conference on Computational Complexity (CCC), CCC'12, pages 74-84, Washington, DC, USA, 2012. IEEE Computer Society. URL: http://dx.doi.org/10.1109/CCC.2012.36.
  18. Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On problems equivalent to (min, +)-convolution. CoRR, abs/1702.07669, 2017. URL: http://arxiv.org/abs/1702.07669.
  19. Werner Fenchel. On conjugate convex functions. Canad. J. Math, 1(73-77), 1949. Google Scholar
  20. Michael L. Fredman. How good is the information theory bound in sorting? Theor. Comput. Sci., 1(4):355-361, 1976. URL: http://dx.doi.org/10.1016/0304-3975(76)90078-5.
  21. Michael L. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. Comput., 5(1):83-89, 1976. URL: http://dx.doi.org/10.1137/0205006.
  22. Anka Gajentaan and Mark H. Overmars. On a class of o(n²) problems in computational geometry. Comput. Geom., 5:165-185, 1995. URL: http://dx.doi.org/10.1016/0925-7721(95)00022-2.
  23. M. R. Garey and D. S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. San Francisco: Freeman, 1979. Google Scholar
  24. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. How hard is it to find (honest) witnesses? In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 45:1-45:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.45.
  25. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  26. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  27. Klaus Jansen and Stefan E. J. Kraft. A Faster FPTAS for the Unbounded Knapsack Problem. In Zsuzsanna Lipták and William F. Smyth, editors, Combinatorial Algorithms: 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers, pages 274-286, Cham, 2016. Springer International Publishing. URL: http://dx.doi.org/10.1007/978-3-319-29516-9_23.
  28. Hans Kellerer and Ulrich Pferschy. Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem. Journal of Combinatorial Optimization, 8(1):5-11, 2004. URL: http://dx.doi.org/10.1023/B:JOCO.0000021934.29833.6b.
  29. Eduardo Sany Laber, Wilfredo Bardales Roncalla, and Ferdinando Cicalese. On lower bounds for the maximum consecutive subsums problem and the (min, +)-convolution. In 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29 - July 4, 2014, pages 1807-1811. IEEE, 2014. URL: http://dx.doi.org/10.1109/ISIT.2014.6875145.
  30. Yves Lucet. Faster than the Fast Legendre Transform, the Linear-time Legendre Transform. Numerical Algorithms, 16(2):171-185, 1997. URL: http://dx.doi.org/10.1023/A:1019191114493.
  31. Tanaeem M. Moosa and M. Sohel Rahman. Indexing permutations for binary strings. Inf. Process. Lett., 110(18-19):795-798, 2010. URL: http://dx.doi.org/10.1016/j.ipl.2010.06.012.
  32. Christos H. Papadimitriou. Computational complexity. Addison-Wesley, 1994. Google Scholar
  33. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 603-610. ACM, 2010. URL: http://dx.doi.org/10.1145/1806689.1806772.
  34. Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362-391, June 1983. URL: http://dx.doi.org/10.1016/0022-0000(83)90006-5.
  35. Godfried Toussaint. The geometry of musical rhythm. In Jin Akiyama, Mikio Kano, and Xuehou Tan, editors, Discrete and Computational Geometry: Japanese Conference, JCDCG 2004, Tokyo, Japan, October 8-11, 2004, Revised Selected Papers, pages 198-212, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/11589440_20.
  36. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.023.
  37. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC'14, pages 664-673, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2591796.2591811.
  38. Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In Thore Husfeldt and Iyad A. Kanj, editors, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, volume 43 of LIPIcs, pages 17-29. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.17.
  39. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM Journal on Computing, 42(3):831-854, 2013. Google Scholar
  40. Uri Zwick. All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms. In Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on, pages 310-319. IEEE, 1998. 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