{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:30Z","timestamp":1750306110676,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["022.005.025,639.021.438, and 639.022.211"],"award-info":[{"award-number":["022.005.025,639.021.438, and 639.022.211"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["617951"],"award-info":[{"award-number":["617951"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055467","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"198-209","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Faster space-efficient algorithms for subset sum and k-sum"],"prefix":"10.1145","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shashwat","family":"Garg","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikhil","family":"Vyas","sequence":"additional","affiliation":[{"name":"IIT Bombay, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Mikl\u00f3s Ajtai. 2005.  Mikl\u00f3s Ajtai. 2005."},{"key":"e_1_3_2_2_2_1","volume-title":"Theory of Computing 1, 8","author":"Time Lower A","year":"2005","unstructured":"A Non-linear Time Lower Bound for Boolean Branching Programs . Theory of Computing 1, 8 ( 2005 ), 149\u2013176. DOI:https:\/\/ A Non-linear Time Lower Bound for Boolean Branching Programs. Theory of Computing 1, 8 (2005), 149\u2013176. DOI:https:\/\/"},{"key":"e_1_3_2_2_3_1","unstructured":"Sanjeev Arora and Boaz Barak. 2009.  Sanjeev Arora and Boaz Barak. 2009."},{"key":"e_1_3_2_2_4_1","unstructured":"Computational Complexity - A Modern Approach. Cambridge University Press. http:\/\/www.cambridge.org\/catalogue\/ catalogue.asp?isbn=9780521424264   Computational Complexity - A Modern Approach. Cambridge University Press. http:\/\/www.cambridge.org\/catalogue\/ catalogue.asp?isbn=9780521424264"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_5"},{"key":"e_1_3_2_2_6_1","volume-title":"Subset Sum in the Absence of Concentration. In Symposium on Theoretical Aspects of Computer Science, STACS. 48\u201361","author":"Austrin Per","year":"2015","unstructured":"Per Austrin , Petteri Kaski , Mikko Koivisto , and Jesper Nederlof . 2015 . Subset Sum in the Absence of Concentration. In Symposium on Theoretical Aspects of Computer Science, STACS. 48\u201361 . Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. 2015. Subset Sum in the Absence of Concentration. In Symposium on Theoretical Aspects of Computer Science, STACS. 48\u201361."},{"key":"e_1_3_2_2_7_1","unstructured":"Per Austrin Petteri Kaski Mikko Koivisto and Jesper Nederlof. 2016.  Per Austrin Petteri Kaski Mikko Koivisto and Jesper Nederlof. 2016."},{"volume-title":"Subset Sum May Be the Hardest. In Symposium on Theoretical Aspects of Computer Science, STACS. 13:1\u201313:14","author":"Dense","key":"e_1_3_2_2_8_1","unstructured":"Dense Subset Sum May Be the Hardest. In Symposium on Theoretical Aspects of Computer Science, STACS. 13:1\u201313:14 . Dense Subset Sum May Be the Hardest. In Symposium on Theoretical Aspects of Computer Science, STACS. 13:1\u201313:14."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541316"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.39"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Anja Becker Jean-S\u00e9bastien Coron and Antoine Joux. 2011. Improved Generic Algorithms for Hard Knapsacks. In Advances in Cryptology - EUROCRYPT. 364\u2013 385.   Anja Becker Jean-S\u00e9bastien Coron and Antoine Joux. 2011. Improved Generic Algorithms for Hard Knapsacks. In Advances in Cryptology - EUROCRYPT. 364\u2013 385.","DOI":"10.1007\/978-3-642-20465-4_21"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01201999"},{"key":"e_1_3_2_2_13_1","unstructured":"Marek Cygan Fedor Fomin Bart M.P. Jansen Lukasz Kowalik Daniel Lokshtanov Daniel Marx Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2014. Open problems for FPT School (link). (2014).  Marek Cygan Fedor Fomin Bart M.P. Jansen Lukasz Kowalik Daniel Lokshtanov Daniel Marx Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2014. Open problems for FPT School (link). (2014)."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_42"},{"key":"e_1_3_2_2_15_1","unstructured":"Rodney G. Downey Michael R. Fellows and Frank K. H. A. Dehne (Eds.). 2004.  Rodney G. Downey Michael R. Fellows and Frank K. H. A. Dehne (Eds.). 2004."},{"key":"e_1_3_2_2_16_1","unstructured":"Parameterized and Exact Computation IWPEC.  Parameterized and Exact Computation IWPEC."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_25"},{"key":"e_1_3_2_2_18_1","volume-title":"Fomin and Dieter Kratsch","author":"Fedor","year":"2010","unstructured":"Fedor V. Fomin and Dieter Kratsch . 2010 . Fedor V. Fomin and Dieter Kratsch. 2010."},{"key":"e_1_3_2_2_19_1","unstructured":"Exact Exponential Algorithms. Springer. DOI:https:\/\/   Exact Exponential Algorithms. Springer. DOI:https:\/\/"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_12"},{"key":"e_1_3_2_2_22_1","unstructured":"Russell Impagliazzo Shachar Lovett Ramamohan Paturi and Stefan Schneider. 2014.  Russell Impagliazzo Shachar Lovett Ramamohan Paturi and Stefan Schneider. 2014."},{"key":"e_1_3_2_2_23_1","volume-title":"CoRR abs\/1401.5512","author":"Linear Integer Linear","year":"2014","unstructured":"0-1 Integer Linear Programming with a Linear Number of Constraints . CoRR abs\/1401.5512 ( 2014 ). http:\/\/arxiv.org\/abs\/1401.5512 0-1 Integer Linear Programming with a Linear Number of Constraints. CoRR abs\/1401.5512 (2014). http:\/\/arxiv.org\/abs\/1401.5512"},{"key":"e_1_3_2_2_24_1","unstructured":"Russell Impagliazzo and Moni Naor. 1996.  Russell Impagliazzo and Moni Naor. 1996."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00189260"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_21"},{"key":"e_1_3_2_2_27_1","unstructured":"Antoine Joux. 2009.  Antoine Joux. 2009."},{"edition":"1","volume-title":"Algorithmic Cryptanalysis","key":"e_1_3_2_2_28_1","unstructured":"Algorithmic Cryptanalysis ( 1 st ed.). Chapman & amp; Hall\/CRC. Algorithmic Cryptanalysis (1st ed.). Chapman & Hall\/CRC."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33293-7_15"},{"key":"e_1_3_2_2_30_1","unstructured":"Donald E. Knuth. 1981.  Donald E. Knuth. 1981."},{"volume-title":"Seminumerical Algorithms","key":"e_1_3_2_2_31_1","unstructured":"Seminumerical Algorithms ( second ed.). The Art of Computer Programming, Vol . 2. Addison-Wesley , Reading, Massachusetts. Seminumerical Algorithms (second ed.). The Art of Computer Programming, Vol. 2. Addison-Wesley, Reading, Massachusetts."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.2461"},{"key":"e_1_3_2_2_33_1","unstructured":"Anany V. Levitin. 2002.  Anany V. Levitin. 2002."},{"volume-title":"Addison-Wesley Longman Publishing Co","author":"Design Introduction","key":"e_1_3_2_2_34_1","unstructured":"Introduction to the Design and Analysis of Algorithms . Addison-Wesley Longman Publishing Co ., Inc., Boston, MA, USA. Introduction to the Design and Analysis of Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA."},{"key":"e_1_3_2_2_35_1","first-page":"1","article-title":"Deterministic Time-Space Trade-Offs for k-Sum","volume":"58","author":"Lincoln Andrea","year":"2016","unstructured":"Andrea Lincoln , Virginia Vassilevska Williams , Joshua R. Wang , and R. Ryan Williams . 2016 . Deterministic Time-Space Trade-Offs for k-Sum . In ICALP. 58 : 1 \u2013 58 :14. Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. 2016. Deterministic Time-Space Trade-Offs for k-Sum. In ICALP. 58:1\u2013 58:14.","journal-title":"ICALP."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806735"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_62"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"e_1_3_2_2_39_1","unstructured":"Noam Nisan. 1993.  Noam Nisan. 1993."},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90258-U"},{"key":"e_1_3_2_2_41_1","unstructured":"Andrew M. Odlyzko. 1990.  Andrew M. Odlyzko. 1990."},{"key":"e_1_3_2_2_42_1","unstructured":"The rise and fall of knapsack cryptosystems. In Cryptology and Computational Number Theory. A.M.S 75\u201388.  The rise and fall of knapsack cryptosystems. In Cryptology and Computational Number Theory. A.M.S 75\u201388."},{"key":"e_1_3_2_2_43_1","unstructured":"Mihai Patrascu and Ryan Williams. 2010.  Mihai Patrascu and Ryan Williams. 2010."},{"volume-title":"Possibility of Faster SAT Algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA.","author":"On","key":"e_1_3_2_2_44_1","unstructured":"On the Possibility of Faster SAT Algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. On the Possibility of Faster SAT Algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA."},{"key":"e_1_3_2_2_45_1","volume-title":"Conference on Computational Complexity. 128\u2013149","author":"Saks Michael E.","year":"1996","unstructured":"Michael E. Saks . 1996 . Randomization and Derandomization in Space_Bounded Computation . In Conference on Computational Complexity. 128\u2013149 . Michael E. Saks. 1996. Randomization and Derandomization in Space_Bounded Computation. In Conference on Computational Complexity. 128\u2013149."},{"key":"e_1_3_2_2_46_1","unstructured":"Richard Schroeppel and Adi Shamir. 1981.  Richard Schroeppel and Adi Shamir. 1981."},{"key":"e_1_3_2_2_47_1","volume-title":"456\u2013464. DOI:https:\/\/","author":"A T","year":"1981","unstructured":"A T = O(2 n\/2 ), S = O(2 n\/4 ) Algorithm for Certain NP- Complete Problems . SIAM J. Comput . 10, 3 ( 1981 ), 456\u2013464. DOI:https:\/\/ A T = O(2 n\/2 ), S = O(2 n\/4 ) Algorithm for Certain NP-Complete Problems. SIAM J. Comput. 10, 3 (1981), 456\u2013464. DOI:https:\/\/"},{"key":"e_1_3_2_2_48_1","volume-title":"Wiener","author":"van Oorschot Paul C.","year":"1999","unstructured":"Paul C. van Oorschot and Michael J . Wiener . 1999 . Paul C. van Oorschot and Michael J. Wiener. 1999."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00003816"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055814"},{"key":"e_1_3_2_2_51_1","volume-title":"Space-Efficient Randomized Algorithms for K-Sum. In European Symposium on Algorithms - ESA. 810\u2013829","author":"Wang Joshua R.","year":"2014","unstructured":"Joshua R. Wang . 2014 . Space-Efficient Randomized Algorithms for K-Sum. In European Symposium on Algorithms - ESA. 810\u2013829 . Joshua R. Wang. 2014. Space-Efficient Randomized Algorithms for K-Sum. In European Symposium on Algorithms - ESA. 810\u2013829."},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591858"}],"event":{"name":"STOC '17: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Montreal Canada","acronym":"STOC '17"},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055467","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055467","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055467"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":52,"alternative-id":["10.1145\/3055399.3055467","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055467","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}