{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T04:35:53Z","timestamp":1768538153476,"version":"3.49.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T00:00:00Z","timestamp":1546905600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council"},{"name":"European Union's Horizon 2020 research and innovation programme","award":["677651"],"award-info":[{"award-number":["677651"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>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\u2014reductions from a problem assumed to be hard. The hard problems include 3SUM, All-Pairs Shortest Path, SAT, Orthogonal Vectors, and others.<\/jats:p>\n          <jats:p>\n            In the (min ,+)-convolution problem, the goal is to compute a sequence (\n            <jats:italic>c<\/jats:italic>\n            [\n            <jats:italic>i<\/jats:italic>\n            ])\n            <jats:sup>n-1<\/jats:sup>\n            <jats:sub>i=0<\/jats:sub>\n            , where\n            <jats:italic>c<\/jats:italic>\n            [\n            <jats:italic>k<\/jats:italic>\n            ] = min\n            <jats:sub>\n              i=0,\u2026; ,\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            {\n            <jats:italic>a<\/jats:italic>\n            [\n            <jats:italic>i<\/jats:italic>\n            ] +\n            <jats:italic>b<\/jats:italic>\n            [\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:italic>i<\/jats:italic>\n            ]}, given sequences (\n            <jats:italic>a<\/jats:italic>\n            [\n            <jats:italic>i<\/jats:italic>\n            ])\n            <jats:sup>n-1<\/jats:sup>\n            <jats:sub>i=0<\/jats:sub>\n            and (\n            <jats:italic>b<\/jats:italic>\n            [\n            <jats:italic>i<\/jats:italic>\n            ])\n            <jats:sup>n-1<\/jats:sup>\n            <jats:sub>i=0<\/jats:sub>\n            . This can easily be done in O(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time, but no\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2-\u03b5<\/jats:sup>\n            ) algorithm is known for \u03b5 &gt; 0. In this article, we undertake a systematic study of the (min ,+)-convolution problem as a hardness assumption.\n          <\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3293465","type":"journal-article","created":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T15:53:12Z","timestamp":1546962792000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["On Problems Equivalent to (min,+)-Convolution"],"prefix":"10.1145","volume":"15","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}]},{"given":"Marcin","family":"Mucha","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}]},{"given":"Karol","family":"W\u0119grzycki","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}]},{"given":"Micha\u0142","family":"W\u0142odarczyk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}]}],"member":"320","published-online":{"date-parts":[[2019,1,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_2_1_2_1","volume-title":"SETH-based lower bounds for subset sum and bicriteria path. CoRR abs\/1704.04546","author":"Abboud Amir","year":"2017","unstructured":"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. 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."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039831"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_36"},{"key":"e_1_2_1_7_1","volume-title":"Dynamic Programming","author":"Bellman Richard","unstructured":"Richard Bellman . 1957. Dynamic Programming . Princeton University Press , Princeton, NJ . Richard Bellman. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_17"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039755"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1875616.1875627"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2556794.2557611"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(94)90048-5"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840746"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/LSP.2013.2278147"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA\u201918)","volume":"61","author":"Chan Timothy M.","year":"2018","unstructured":"Timothy M. Chan . 2018 . Approximation schemes for 0-1 knapsack . In Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA\u201918) (OASICS), Raimund Seidel (Ed.) , Vol. 61 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 5:1--5:12. Timothy M. Chan. 2018. Approximation schemes for 0-1 knapsack. In Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA\u201918) (OASICS), Raimund Seidel (Ed.), Vol. 61. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 5:1--5:12."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746568"},{"key":"e_1_2_1_18_1","volume-title":"In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","volume":"80","author":"Chatzigiannakis Ioannis","year":"2017","unstructured":"Ioannis Chatzigiannakis , Piotr Indyk , Fabian Kuhn , and Anca Muscholl ( Eds .). 2017 . In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917) , LIPIcs, Vol. 80 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-041-5. Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.). 2017. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917), LIPIcs, Vol. 80. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-041-5."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.05.032"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.36"},{"key":"e_1_2_1_21_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_22_1","unstructured":"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.  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."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0841"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1949-007-x"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90078-5"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205006"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_2_1_28_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.   M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","volume":"57","author":"Goldstein Isaac","year":"2016","unstructured":"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\u201916) , LIPIcs, Vol. 57 , Piotr Sankowski and Christos D. Zaroliagis (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 45:1--45:16. 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\u201916), LIPIcs, Vol. 57, Piotr Sankowski and Christos D. Zaroliagis (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 45:1--45:16."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_33_1","volume-title":"Kraft","author":"Jansen Klaus","year":"2016","unstructured":"Klaus Jansen and Stefan E. J . Kraft . 2016 . A Faster FPTAS for the Unbounded Knapsack Problem. Springer International Publishing , Cham, 274--286. Klaus Jansen and Stefan E. J. Kraft. 2016. A Faster FPTAS for the Unbounded Knapsack Problem. Springer International Publishing, Cham, 274--286."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039754"},{"key":"e_1_2_1_35_1","unstructured":"Marvin K\u00fcnnemann 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.  Marvin K\u00fcnnemann 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."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2014.6875145"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3170442"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019191114493"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.06.012"},{"key":"e_1_2_1_40_1","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","unstructured":"Christos H. Papadimitriou . 1994. Computational Complexity . Addison-Wesley . Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/11589440_20"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591811"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915)","volume":"43","author":"Williams Virginia Vassilevska","year":"2015","unstructured":"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\u201915) , LIPIcs, Vol. 43 , Thore Husfeldt and Iyad A. Kanj (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 17--29. 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\u201915), LIPIcs, Vol. 43, Thore Husfeldt and Iyad A. Kanj (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 17--29."},{"key":"e_1_2_1_48_1","volume-title":"On some fine-grained questions in algorithms and complexity. To appear at ICM","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams . 2018. On some fine-grained questions in algorithms and complexity. To appear at ICM 2018 . Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. To appear at ICM 2018."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076619X"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796456"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293465","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293465","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:01Z","timestamp":1750208521000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293465"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,8]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3293465"],"URL":"https:\/\/doi.org\/10.1145\/3293465","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,8]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}