On Problems Equivalent to (min,+)-Convolution

Abstract

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

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

First, we establish the 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 problem has been used as a building block in algorithms for many problems, notably problems in stringology. It has also appeared as an ad hoc hardness assumption. Second, we investigate some of these connections and provide new reductions and other results. We also explain why replacing this assumption with the Strong Exponential Time Hypothesis might not be possible for some problems.

References

1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2015. Tight hardness results for LCS and other sequence similarity measures. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS’15), Venkatesan Guruswami (Ed.). IEEE Computer Society, 59--78.
2. Amir Abboud, Karl Bringmann, and Dvir Shabtay Danny Hermelin. 2017. SETH-based lower bounds for subset sum and bicriteria path. CoRR abs/1704.04546 (2017). http://arxiv.org/abs/1704.04546.
3. Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-coding. J. ACM 42, 4 (1995), 844--856.
4. Arturs Backurs and Piotr Indyk. 2015. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC’15), Rocco A. Servedio and Ronitt Rubinfeld (Eds.). ACM, 51--58.
5. Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. 2017. Better approximations for tree sparsity in nearly-linear time. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2215--2229.
6. Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. 2005. Subquadratic algorithms for 3SUM. In Proceedings of the 9th International Conference on Algorithms and Data Structures (WADS’05). Springer-Verlag, Berlin, Heidelberg, 409--421.
7. Richard Bellman. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
8. David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian. 2006. Necklaces, Convolutions, and X + Y. Springer, Berlin, 160--171.
9. Karl Bringmann. 2017. A near-linear pseudopolynomial time algorithm for subset sum. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1073--1084.
10. Karl Bringmann and Marvin Künnemann. 2015. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS’15), Venkatesan Guruswami (Ed.). IEEE Computer Society, 79--97.
11. Peter Burcsi, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. 2010. On table arrangements, scrabble freaks, and jumbled pattern matching. In Proceedings of the 5th International Conference, Fun with Algorithms (FUN’10), Lecture Notes in Computer Science, Vol. 6099, Paolo Boldi and Luisa Gargano (Eds.). Springer, 89--101.
12. Peter Burcsi, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. 2012. On approximate jumbled pattern matching in strings. Theory Comput. Syst. 50, 1 (2012), 35--51.
13. Michael R. Bussieck, Hannes Hassler, Gerhard J. Woeginger, and Uwe T. Zimmermann. 1994. Fast algorithms for the maximum convolution problem. Oper. Res. Lett. 15, 3 (1994), 133--141.
14. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. 2016. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Madhu Sudan (Ed.). ACM, 261--270.
15. Coralia Cartis and Andrew Thompson. 2013. An exact tree projection algorithm for wavelets. IEEE Signal Process. Lett. 20, 11 (2013), 1026--1029.
16. Timothy M. Chan. 2018. Approximation schemes for 0-1 knapsack. In Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA’18) (OASICS), Raimund Seidel (Ed.), Vol. 61. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 5:1--5:12.
17. Timothy M. Chan and Moshe Lewenstein. 2015. Clustered integer 3SUM via additive combinatorics. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC’15). ACM, New York, 31--40.
18. Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.). 2017. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP’17), LIPIcs, Vol. 80. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. http://www.dagstuhl.de/dagpub/978-3-95977-041-5.
19. Ferdinando Cicalese, Eduardo Sany Laber, Oren Weimann, and Raphael Yuster. 2014. Approximating the maximum consecutive subsums of a sequence. Theor. Comput. Sci. 525 (2014), 130--137.
20. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dańiel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlstrom. 2012. On problems as hard as CNF-SAT. In Proceedings of the 2012 IEEE Conference on Computational Complexity (CCC’12). IEEE Computer Society, 74--84.
21. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer.
22. Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. 2017. On problems equivalent to (min, +)-convolution, see Chatzigiannakis et al. {18}, 22:1--22:15.
23. David Eppstein. 1997. Minimum range balanced cuts via dynamic subset sums. J. Algorithms 23, 2 (1997), 375--385.
24. Werner Fenchel. 1949. On conjugate convex functions. Canad. J. Math 1, 73--77 (1949).
25. Michael L. Fredman. 1976. How good is the information theory bound in sorting? Theor. Comput. Sci. 1, 4 (1976), 355--361.
26. Michael L. Fredman. 1976. New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5, 1 (1976), 83--89.
27. Anka Gajentaan and Mark H. Overmars. 1995. On a class of O(n²) problems in computational geometry. Comput. Geom. 5 (1995), 165--185.
28. M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
29. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. 2016. How hard is it to find (honest) witnesses? In Proceedings of the 24th Annual European Symposium on Algorithms (ESA’16), LIPIcs, Vol. 57, Piotr Sankowski and Christos D. Zaroliagis (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 45:1--45:16.
30. Ellis Horowitz and Sartaj Sahni. 1974. Computing partitions with applications to the knapsack problem. J. ACM 21, 2 (1974), 277--292.
31. Russell Impagliazzo and Ramamohan Paturi. 2001. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 2 (2001), 367--375.
32. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity?J. Comput. Syst. Sci. 63, 4 (2001), 512--530.
33. Klaus Jansen and Stefan E. J. Kraft. 2016. A Faster FPTAS for the Unbounded Knapsack Problem. Springer International Publishing, Cham, 274--286.
34. Konstantinos Koiliaris and Chao Xu. 2017. A faster pseudopolynomial time algorithm for subset sum. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1062--1072.
35. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. 2017. On the fine-grained complexity of one-dimensional dynamic programming, see Chatzigiannakis et al. {18}, 21:1--21:15.
36. Eduardo Sany Laber, Wilfredo Bardales Roncalla, and Ferdinando Cicalese. 2014. On lower bounds for the maximum consecutive subsums problem and the (min, +)-convolution. In Proceedings of the 2014 IEEE International Symposium on Information Theory. IEEE, 1807--1811.
37. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. 2018. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms 14, 2 (2018), 13:1--13:30.
38. Yves Lucet. 1997. Faster than the fast Legendre transform, the linear-time legendre transform. Numer. Algorithms 16, 2 (1997), 171--185.
39. Tanaeem M. Moosa and M. Sohel Rahman. 2010. Indexing permutations for binary strings. Inf. Process. Lett. 110, 18-19 (2010), 795--798.
40. Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley.
41. Mihai Patrascu. 2010. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’10), Leonard J. Schulman (Ed.). ACM, 603--610.
42. Daniel D. Sleator and Robert Endre Tarjan. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 3 (June 1983), 362--391.
43. Godfried Toussaint. 2005. The Geometry of Musical Rhythm. Springer, Berlin, 198--212.
44. Virginia Vassilevska and Williams Ryan Williams. 2010. Subcubic equivalences between path, matrix and triangle problems. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS’10).
45. Ryan Williams. 2005. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348, 2-3 (2005), 357--365.
46. Ryan Williams. 2014. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC’14). ACM, New York, 664--673.
47. Virginia Vassilevska Williams. 2015. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC’15), LIPIcs, Vol. 43, Thore Husfeldt and Iyad A. Kanj (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 17--29.
48. Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. To appear at ICM 2018.
49. Virginia Vassilevska Williams and Ryan Williams. 2010. Subcubic equivalences between path, matrix and triangle problems. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS’10). IEEE Computer Society, 645--654.
50. Virginia Vassilevska Williams and Ryan Williams. 2013. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42, 3 (2013), 831--854.
51. Uri Zwick. 1998. All pairs shortest paths in weighted directed graphs—exact and almost exact algorithms. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE, 310--319.

Index Terms

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes

    • Problems, reductions and completeness

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming