{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:49Z","timestamp":1781078209117,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Polish National Science Center (NCN)","award":["2016\/21\/N\/ST6\/01468 and 2018\/28\/T\/ST6\/00084"],"award-info":[{"award-number":["2016\/21\/N\/ST6\/01468 and 2018\/28\/T\/ST6\/00084"]}]},{"name":"European Research Council (ERC)","award":["853234"],"award-info":[{"award-number":["853234"]}]},{"name":"Foundation for Polish Science (FNP)"},{"name":"European Research Council (ERC)","award":["677651"],"award-info":[{"award-number":["677651"]}]},{"name":"European Research Council (ERC)","award":["850979"],"award-info":[{"award-number":["850979"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451024","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1670-1683","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Improving Schroeppel and Shamir\u2019s algorithm for subset sum via orthogonal vectors"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1848-0076","authenticated-orcid":false,"given":"Jesper","family":"Nederlof","sequence":"first","affiliation":[{"name":"Utrecht University, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9746-5733","authenticated-orcid":false,"given":"Karol","family":"W\u0119grzycki","sequence":"additional","affiliation":[{"name":"Saarland University, Germany \/ MPI-INF, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Amir Abboud. 2020. personal communication."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.3"},{"key":"e_1_3_2_1_3_1","volume-title":"40th International Colloquium, ICALP","author":"Abboud Amir","year":"2013","unstructured":"Amir Abboud and Kevin Lewi. 2013. Exact Weight Subgraphs and the k-Sum Conjecture. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013. Lecture Notes in Computer Science. 7965, Springer. Pages 1\u201312."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.17"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_2_1_6_1","first-page":"56","volume-title":"40th International Colloquium, ICALP","author":"Austrin Per","year":"2013","unstructured":"Per Austrin, Petteri Kaski, Mikko Koivisto, and Jussi M\u00e4\u00e4tt\u00e4. 2013. Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013. Pages 45\u201356."},{"key":"e_1_3_2_1_7_1","first-page":"61","volume-title":"Subset Sum in the Absence of Concentration. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS","author":"Austrin Per","year":"2015","unstructured":"Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. 2015. Subset Sum in the Absence of Concentration. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015. Pages 48\u201361."},{"key":"e_1_3_2_1_8_1","first-page":"14","volume-title":"Dense Subset Sum May Be the Hardest. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS","author":"Austrin Per","year":"2016","unstructured":"Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. 2016. Dense Subset Sum May Be the Hardest. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016. Pages 13:1\u201313:14."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1158203"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings. Pages 364\u2013385","author":"Becker Anja","year":"2011","unstructured":"Anja Becker, Jean-S\u00e9bastien Coron, and Antoine Joux. 2011. Improved Generic Algorithms for Hard Knapsacks. In Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Proceedings. Pages 364\u2013385."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings.","author":"Bj\u00f6rklund Andreas","year":"2009","unstructured":"Andreas Bj\u00f6rklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Amos Fiat, and Peter Sanders. 2009. Counting Paths and Packings in Halves. In Algorithms - ESA 2009, 17th Annual European Symposium. Proceedings."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01904851"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.69"},{"key":"e_1_3_2_1_16_1","unstructured":"Karl Bringmann. 2020. personal communication."},{"key":"e_1_3_2_1_17_1","first-page":"1255","volume-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA","author":"Timothy","year":"2016","unstructured":"Timothy M. Chan and Ryan Williams. 2016. Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. SIAM. Pages 1246\u20131255."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310437"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"key":"e_1_3_2_1_20_1","volume-title":"Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference. Proceedings.","author":"Dinur Itai","unstructured":"Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir. 2012. Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems. In Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference. Proceedings."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196275"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings. Pages 235\u2013256","author":"Howgrave-Graham Nick","year":"2010","unstructured":"Nick Howgrave-Graham and Antoine Joux. 2010. New Generic Algorithms for Hard Knapsacks. In Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Proceedings. Pages 235\u2013256."},{"key":"e_1_3_2_1_25_1","first-page":"6","volume-title":"2nd Symposium on Simplicity in Algorithms, SOSA@SODA","author":"Jin Ce","year":"2019","unstructured":"Ce Jin and Hongxun Wu. 2019. A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum. In 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019. Pages 17:1\u201317:6."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039754"},{"key":"e_1_3_2_1_27_1","first-page":"1","article-title":"Lower bounds based on the exponential time hypothesis","volume":"105","author":"Lokshtanov Daniel","year":"2011","unstructured":"Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bulletin of the European Association for Theoretical Computer Science EATCS, 105, 1, 2011.","journal-title":"Bulletin of the European Association for Theoretical Computer Science EATCS"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806735"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the WG '83, International Workshop on Graphtheoretic Concepts in Computer Science. Pages 241\u2013251","author":"Monien Burkhard","year":"1983","unstructured":"Burkhard Monien. 1983. The Complexity of Determining Paths of Length k. In Proceedings of the WG '83, International Workshop on Graphtheoretic Concepts in Computer Science. Pages 241\u2013251."},{"key":"e_1_3_2_1_30_1","volume-title":"Equal-Subset-Sum Faster Than the Meet-in-the-Middle. In 27th Annual European Symposium on Algorithms, ESA","author":"Mucha Marcin","year":"2019","unstructured":"Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, and Karol W\\k egrzycki. 2019. Equal-Subset-Sum Faster Than the Meet-in-the-Middle. In 27th Annual European Symposium on Algorithms, ESA 2019."},{"key":"e_1_3_2_1_31_1","volume-title":"24th Annual European Symposium on Algorithms, ESA","author":"Nederlof Jesper","year":"2016","unstructured":"Jesper Nederlof. 2016. Finding Large Set Covers Faster via the Representation Method. In 24th Annual European Symposium on Algorithms, ESA 2016."},{"key":"e_1_3_2_1_32_1","volume-title":"Festschrift Dedicated to the 60th Birthday of Hans Bodlaender","author":"Nederlof Jesper","unstructured":"Jesper Nederlof. 2020. Algorithms for NP-Hard Problems via Rank-related Parameters of Matrices. In Festschrift Dedicated to the 60th Birthday of Hans Bodlaender. Springer."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.102"},{"key":"e_1_3_2_1_34_1","first-page":"727","volume-title":"MFCS","author":"Nederlof Jesper","year":"2012","unstructured":"Jesper Nederlof, Erik Jan van Leeuwen, and Ruben van der Zwaan. 2012. Reducing a Target Interval to a Few Exact Queries. In Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012. Pages 718\u2013727."},{"key":"e_1_3_2_1_35_1","volume-title":"Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors","author":"Nederlof Jesper","year":"2020","unstructured":"Jesper Nederlof and Karol W\\k egrzycki. 2020. Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors. 2020. arxiv:2010.08576"},{"key":"e_1_3_2_1_36_1","volume-title":"Communication Complexity: and Applications","author":"Rao Anup","unstructured":"Anup Rao and Amir Yehudayoff. 2020. Communication Complexity: and Applications. Cambridge University Press."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210033"},{"key":"e_1_3_2_1_38_1","first-page":"34","volume-title":"Proceedings of the International Congress of Mathematicians (ICM","author":"Vassilevska-Williams Virginia","year":"2018","unstructured":"Virginia Vassilevska-Williams. 2018. On Some Fine-Grained Questions in Algorithms and Complexity. In Proceedings of the International Congress of Mathematicians (ICM 2018). Pages 3447\u201334."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451024","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451024","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451024"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":39,"alternative-id":["10.1145\/3406325.3451024","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451024","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}