{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:31:53Z","timestamp":1787340713553,"version":"build-2736575974"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["617951"],"award-info":[{"award-number":["617951"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.022.211"],"award-info":[{"award-number":["639.022.211"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["022.005.025"],"award-info":[{"award-number":["022.005.025"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.021.438"],"award-info":[{"award-number":["639.021.438"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We present randomized algorithms that solve subset sum and knapsack instances with $n$ items in $O^*(2^{0.86n})$ time, where the $O^*(\\cdot)$ notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve binary integer programming on $n$ variables with few constraints in a similar running time. We also show that for any constant $k\\geq 2$, random instances of $k$-sum can be solved using $O(n^{k-0.5}\\mathrm{polylog}(n))$ time and $O(\\log n)$ space, without the assumption of random access to random bits. Underlying these results is an algorithm that determines whether two given lists of length $n$ with integers bounded by a polynomial in $n$ share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using $O(\\log n)$ space significantly faster than the trivial $O(n^2)$ time algorithm if no value occurs too often in the same list.<\/jats:p>","DOI":"10.1137\/17m1158203","type":"journal-article","created":{"date-parts":[[2018,10,4]],"date-time":"2018-10-04T11:57:54Z","timestamp":1538654274000},"page":"1755-1777","source":"Crossref","is-referenced-by-count":10,"title":["Faster Space-Efficient Algorithms for Subset Sum,  $k$-Sum, and Related Problems"],"prefix":"10.1137","volume":"47","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shashwat","family":"Garg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1848-0076","authenticated-orcid":true,"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikhil","family":"Vyas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,10,4]]},"reference":[{"key":"atypb1","unstructured":"A. Abboud, K. Bringmann, D. Hermelin, and D. Shabtay,\n                      SETH-Based Lower Bounds for Subset Sum and Bicriteria Path\n                      , preprint,https:\/\/arxiv.org\/abs\/1704.04546, 2017."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a008"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"S. Arora and B. Barak,\n                      Computational Complexity-A Modern Approach\n                      , Cambridge University Press, Cambridge, UK, 2009.","DOI":"10.1017\/CBO9780511804090"},{"key":"atypb5","first-page":"45","author":"Austrin P.","year":"2013","journal-title":"Heidelberg"},{"key":"atypb6","first-page":"48","author":"Austrin P.","year":"2015","journal-title":"Wadern"},{"key":"atypb7","first-page":"13","author":"Austrin P.","year":"2016","journal-title":"Wadern"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2688378"},{"key":"atypb9","first-page":"198","author":"Bansal N.","year":"2017","journal-title":"New York"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"P. Beame, R. Clifford, and W. Machmouchi,\n                      Element distinctness, frequency moments, and sliding windows\n                      , in Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Los Alamitos, CA, 2013, pp. 290-299.","DOI":"10.1109\/FOCS.2013.39"},{"key":"atypb11","first-page":"364","author":"Becker A.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321111"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01201999"},{"key":"atypb14","unstructured":"M. Cygan, F. Fomin, B. M. P. Jansen, \u0141. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Open Problems for FPT School,\n                      http:\/\/fptschool.mimuw.edu.pl\/opl.pdf, 2014."},{"key":"atypb15","first-page":"719","author":"Dinur I.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"R. G. Downey, M. R. Fellows, and F. K. H. A. Dehne, eds.\n                      Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC\n                      ), Bergen, Norway, 2004.","DOI":"10.1007\/b100584"},{"key":"atypb17","first-page":"305","author":"Flaxman A.","year":"2005","journal-title":"Berlin"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"F. V. Fomin and D. Kratsch,\n                      Exact Exponential Algorithms\n                      , Texts in Theoretical Computer Science. An EATCS Series, Springer, Berlin, 2010,https:\/\/doi.org\/10.1007\/978-3-642-16533-7.","DOI":"10.1007\/978-3-642-16533-7"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"atypb20","first-page":"235","author":"Howgrave-Graham N.","year":"2010","journal-title":"Berlin"},{"key":"atypb21","unstructured":"R. Impagliazzo, S. Lovett, R. Paturi, and S. Schneider,\n                      0-1 Integer Linear Programming with a Linear Number of Constraints\n                      , preprint,https:\/\/arxiv.org\/abs\/1401.5512, 2014."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF00189260"},{"key":"atypb23","first-page":"369","author":"Jain A.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"A. Joux,\n                      Algorithmic Cryptanalysis\n                      , Chapman & Hall\/CRC, Boca Raton, FL, 2009.","DOI":"10.1201\/9781420070033"},{"key":"atypb25","first-page":"147","author":"Kaski P.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb26","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming. Vol. 2: Seminumerical Algorithms,\n                      Addison-Wesley, Reading, MA, 1981."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/2455.2461"},{"key":"atypb28","unstructured":"A. V. Levitin,\n                      Introduction to the Design and Analysis of Algorithms\n                      , Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002."},{"key":"atypb29","first-page":"58","author":"Lincoln A.","year":"2016","journal-title":"Wadern"},{"key":"atypb30","first-page":"321","author":"Lokshtanov D.","year":"2010","journal-title":"New York"},{"key":"atypb31","first-page":"718","author":"Nederlof J.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90258-U"},{"key":"atypb34","first-page":"75","author":"Odlyzko A. M.","year":"1990","journal-title":"RI"},{"key":"atypb35","first-page":"1065","author":"Patrascu M.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"M. E. Saks,\n                      Randomization and derandomization in space-bounded computation\n                      , in Proceedings of Computational Complexity (Formerly Structure in Complexity Theory), IEEE, Los Alamitos, CA, 1996, pp. 128-149.","DOI":"10.1109\/CCC.1996.507676"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/0210033"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/PL00003816"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055814"},{"key":"atypb40","first-page":"810","author":"Wang J. R.","year":"2014","journal-title":"Heidelberg"},{"key":"atypb41","first-page":"194","author":"Williams R.","year":"2014","journal-title":"New York"},{"key":"atypb42","first-page":"281","author":"Woeginger G. J.","year":"2004","journal-title":"Berlin"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1158203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:45:10Z","timestamp":1787337910000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1158203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1158203"],"URL":"https:\/\/doi.org\/10.1137\/17m1158203","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}