{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T08:40:24Z","timestamp":1781080824197,"version":"3.54.1"},"reference-count":116,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,1,23]],"date-time":"2022-01-23T00:00:00Z","timestamp":1642896000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1417238, CCF-1528078, and CCF-1514339"],"award-info":[{"award-number":["CCF-1417238, CCF-1528078, and CCF-1514339"]}]},{"name":"BSF","award":["BSF:2012338"],"award-info":[{"award-number":["BSF:2012338"]}]},{"name":"IBM Almaden Research Center and in Stanford University"},{"name":"European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme","award":["850979"],"award-info":[{"award-number":["850979"]}]},{"name":"People Programme (Marie Curie Actions) of the European Union\u2019s Seventh Framework Programme","award":["FP7\/2007-2013"],"award-info":[{"award-number":["FP7\/2007-2013"]}]},{"name":"REA","award":["631163.11"],"award-info":[{"award-number":["631163.11"]}]},{"name":"ISRAEL Science Foundation","award":["551145\/"],"award-info":[{"award-number":["551145\/"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>\n            Subset Sumand\n            <jats:italic>k<\/jats:italic>\n            -SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. An important open problem in this area is to base the hardness of one of these problems on the other.\n          <\/jats:p>\n          <jats:p>\n            Our main result is a tight reduction from\n            <jats:italic>k<\/jats:italic>\n            -SAT to Subset Sum on dense instances, proving that Bellman\u2019s 1962 pseudo-polynomial\n            <jats:italic>O<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            (\n            <jats:italic>T<\/jats:italic>\n            )-time algorithm for Subset Sum on\n            <jats:italic>n<\/jats:italic>\n            numbers and target\u00a0\n            <jats:italic>T<\/jats:italic>\n            cannot be improved to time\n            <jats:italic>T<\/jats:italic>\n            <jats:sup>1-\u03b5<\/jats:sup>\n            \u00b7 2\n            <jats:sup>o(n)<\/jats:sup>\n            for any \u03b5 &gt; 0, unless the Strong Exponential Time Hypothesis (SETH) fails.\n          <\/jats:p>\n          <jats:p>\n            As a corollary, we prove a \u201cDirect-OR\u201d theorem for Subset Sum under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of\n            <jats:italic>N<\/jats:italic>\n            given instances of Subset Sum is a YES instance requires time (\n            <jats:italic>N T<\/jats:italic>\n            )\n            <jats:sup>1-o(1)<\/jats:sup>\n            . As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria\n            <jats:italic>s,t<\/jats:italic>\n            -Path problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset Sum: On graphs with\n            <jats:italic>m<\/jats:italic>\n            edges and edge lengths bounded by\n            <jats:italic>L<\/jats:italic>\n            , we show that the\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>Lm<\/jats:italic>\n            ) pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to \u00d5(\n            <jats:italic>L<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            ), in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).\n          <\/jats:p>","DOI":"10.1145\/3450524","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T05:51:05Z","timestamp":1643003465000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["SETH-based Lower Bounds for Subset Sum and Bicriteria Path"],"prefix":"10.1145","volume":"18","author":[{"given":"Amir","family":"Abboud","sequence":"first","affiliation":[{"name":"IBM Almaden Research Center, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karl","family":"Bringmann","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering and Management, Ben-Gurion University, Beer Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dvir","family":"Shabtay","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering and Management, Ben-Gurion University, Beer Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,23]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch88"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897555"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_1"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_1"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746594"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722146"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_4"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814642"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_10"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800250314"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_5"},{"key":"e_1_3_2_16_2","first-page":"48","volume-title":"Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915)","author":"Austrin Per","year":"2015"},{"key":"e_1_3_2_17_2","first-page":"13:1\u201313:14","volume-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916)","author":"Austrin Per","year":"2016"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.56"},{"key":"e_1_3_2_20_2","first-page":"4311","volume-title":"Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS\u201917)","author":"Backurs Arturs","year":"2017"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055466"},{"key":"e_1_3_2_22_2","first-page":"203","article-title":"Proofs of useful work","volume":"2017","author":"Ball Marshall","year":"2017","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055467"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9036-3"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_9"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488669"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/2008684.2008713"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"e_1_3_2_29_2","volume-title":"Dynamic Programming","author":"Bellman Richard E.","year":"1957"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.11"},{"key":"e_1_3_2_31_2","first-page":"496","volume-title":"Proceedings of the 1st ACM Conference on Innovations in Theoretical Computer Science (ITCS\u201911)","author":"Bhattacharyya Arnab","year":"2011"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/5.4443"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.69"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.36"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2010.05.036"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9550-z"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/110853327"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.6"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_6"},{"key":"e_1_3_2_42_2","first-page":"25:1\u201325:17","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Cardinal Jean","year":"2016"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840746"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06089-7_7"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746568"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.21214"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"issue":"3","key":"e_1_3_2_49_2","first-page":"41","article-title":"On problems as hard as CNF-SAT","volume":"12","author":"Cygan Marek","year":"2016","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_2_50_2","first-page":"403","volume-title":"Handbook of Satisfiability","author":"Dantsin Evgeny","year":"2009"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806725"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_42"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.72"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00205-3"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797315410"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/130910932"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0079-6"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.141"},{"key":"e_1_3_2_60_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP Completeness","author":"Garey Michael R.","year":"1976"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2010.05.017"},{"key":"e_1_3_2_62_2","first-page":"42:1\u201342:13","volume-title":"Proceedings of the 25th Annual European Symposium on Algorithms (ESA\u201917)","author":"Gold Omer","year":"2017"},{"key":"e_1_3_2_63_2","first-page":"45:1\u201345:16","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Goldstein Isaac","year":"2016"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-48782-8_9"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.17.1.36"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10068"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.15.1.42.15151"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_12"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00189260"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9946-9"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_61"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.04.004"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1137\/140952636"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(66)90020-5"},{"key":"e_1_3_2_78_2","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1109\/FOCS.2014.72","volume-title":"Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201914)","author":"J\u00f8rgensen Allan Gr\u00f8nlund","year":"2014"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7"},{"key":"e_1_3_2_81_2","unstructured":"James King. 2004. A survey of 3SUM-hard problems. (2004)."},{"key":"e_1_3_2_82_2","unstructured":"Tomasz Kociumaka Solon P. Pissis and Jakub Radoszewski. 2016. Parameterizing PWM-and profile-matching and knapsack by the feasible-weight solutions count. Retrieved from https:\/\/arXiv:1604.07581."},{"key":"e_1_3_2_83_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.68"},{"key":"e_1_3_2_84_2","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884524"},{"key":"e_1_3_2_85_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.04.018"},{"key":"e_1_3_2_86_2","first-page":"58:1\u201358:14","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","author":"Lincoln Andrea","year":"2016"},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.61"},{"key":"e_1_3_2_88_2","first-page":"41","article-title":"Lower bounds based on the exponential time hypothesis","volume":"105","author":"Lokshtanov Daniel","year":"2011","journal-title":"Bull. EATCS"},{"key":"e_1_3_2_89_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806735"},{"key":"e_1_3_2_90_2","doi-asserted-by":"publisher","DOI":"10.1109\/90.748088"},{"key":"e_1_3_2_91_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(01)00069-4"},{"key":"e_1_3_2_92_2","doi-asserted-by":"publisher","DOI":"10.5555\/98124"},{"key":"e_1_3_2_93_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055927"},{"key":"e_1_3_2_94_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-0191-8"},{"key":"e_1_3_2_95_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.09.002"},{"key":"e_1_3_2_96_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_62"},{"key":"e_1_3_2_97_2","doi-asserted-by":"publisher","DOI":"10.37236\/546"},{"key":"e_1_3_2_98_2","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/042\/1095552"},{"key":"e_1_3_2_99_2","first-page":"1065","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"P\u0103tra\u015fcu Mihai","year":"2010"},{"key":"e_1_3_2_100_2","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066101"},{"key":"e_1_3_2_101_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0989-y"},{"key":"e_1_3_2_102_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.03.002"},{"key":"e_1_3_2_103_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_3_2_104_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2008.02.002"},{"key":"e_1_3_2_105_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_3_2_106_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.omega.2013.07.001"},{"key":"e_1_3_2_107_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1984.1056964"},{"key":"e_1_3_2_108_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3078-3"},{"key":"e_1_3_2_109_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_67"},{"key":"e_1_3_2_110_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.35.1.70"},{"key":"e_1_3_2_111_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_2_112_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.135"},{"key":"e_1_3_2_113_2","first-page":"17","volume-title":"Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915) (LIPIcs)","volume":"43","author":"Williams Virginia Vassilevska","year":"2015"},{"key":"e_1_3_2_114_2","first-page":"455","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC\u201909)","author":"Williams Virginia Vassilevska","year":"2009"},{"key":"e_1_3_2_115_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.03.023"},{"key":"e_1_3_2_116_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2003.5342226"},{"key":"e_1_3_2_117_2","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1007\/978-3-642-55753-8_52","volume-title":"Mathematics \u2014 Key Technology for the Future: Joint Projects between Universities and Industry","author":"Zimmermann U.","year":"2003"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450524","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450524","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450524","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:49Z","timestamp":1750193269000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,23]]},"references-count":116,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3450524"],"URL":"https:\/\/doi.org\/10.1145\/3450524","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,23]]},"assertion":[{"value":"2019-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}