{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T05:58:35Z","timestamp":1770357515293,"version":"3.49.0"},"publisher-location":"Cham","reference-count":69,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031683787","type":"print"},{"value":"9783031683794","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-68379-4_10","type":"book-chapter","created":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T20:17:23Z","timestamp":1723753043000},"page":"315-351","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["k-SUM in\u00a0the\u00a0Sparse Regime: Complexity and\u00a0Applications"],"prefix":"10.1007","author":[{"given":"Shweta","family":"Agrawal","sequence":"first","affiliation":[]},{"given":"Sagnik","family":"Saha","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0610-4455","authenticated-orcid":false,"given":"Nikolaj I.","family":"Schwartzbach","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5817-7691","authenticated-orcid":false,"given":"Akhil","family":"Vanukuri","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6880-795X","authenticated-orcid":false,"given":"Prashant Nalini","family":"Vasudevan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,16]]},"reference":[{"key":"10_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Bringmann, K., Hermelin, D., Shabtay, D.: Seth-based lower bounds for subset sum and bicriteria path. In: Chan, T.M. (ed.) Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, 6\u20139 January 2019, pp. 41\u201357. SIAM (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.3","DOI":"10.1137\/1.9781611975482.3"},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-39206-1_1","volume-title":"Automata, Languages, and Programming","author":"A Abboud","year":"2013","unstructured":"Abboud, A., Lewi, K.: Exact weight subgraphs and the k-sum conjecture. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 1\u201312. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39206-1_1"},{"key":"10_CR3","doi-asserted-by":"publisher","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 434\u2013443 (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.53","DOI":"10.1109\/FOCS.2014.53"},{"key":"10_CR4","unstructured":"Agrawal, S., Saha, S., Schwartzbach, N.I., Vanukuri, A., Vasudevan, P.N.: $$k$$-sum in the sparse regime. Cryptology ePrint Archive, Paper 2023\/488 (2023). https:\/\/eprint.iacr.org\/2023\/488"},{"issue":"2","key":"10_CR5","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/1059513.1059515","volume":"52","author":"N Ailon","year":"2005","unstructured":"Ailon, N., Chazelle, B.: Lower bounds for linear degeneracy testing. J. ACM 52(2), 157\u2013171 (2005). https:\/\/doi.org\/10.1145\/1059513.1059515","journal-title":"J. ACM"},{"key":"10_CR6","doi-asserted-by":"publisher","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), Cambridge, MA, USA, 11\u201314 October 2003, Proceedings, pp. 298\u2013307. IEEE Computer Society (2003). https:\/\/doi.org\/10.1109\/SFCS.2003.1238204","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"10_CR7","doi-asserted-by":"publisher","unstructured":"Alon, N., Chung, F.: Explicit construction of linear sized tolerant networks. Discret. Math. 72(1), 15\u201319 (1988). https:\/\/doi.org\/10.1016\/0012-365X(88)90189-6. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0012365X88901896","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"10_CR8","doi-asserted-by":"publisher","unstructured":"Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: Schulman, L.J. (ed.) Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5\u20138 June 2010, pp. 171\u2013180. ACM (2010). https:\/\/doi.org\/10.1145\/1806689.1806715","DOI":"10.1145\/1806689.1806715"},{"key":"10_CR9","doi-asserted-by":"publisher","unstructured":"Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Average-case fine-grained hardness. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 483\u2013496. Association for Computing Machinery, New York (2017). https:\/\/doi.org\/10.1145\/3055399.3055466","DOI":"10.1145\/3055399.3055466"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/978-3-319-96884-1_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"M Ball","year":"2018","unstructured":"Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Proofs of work from worst-case assumptions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 789\u2013819. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96884-1_26"},{"key":"10_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-22792-9_1","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"B Barak","year":"2011","unstructured":"Barak, B., Dodis, Y., Krawczyk, H., Pereira, O., Pietrzak, K., Standaert, F.-X., Yu, Yu.: Leftover hash lemma, revisited. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 1\u201320. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22792-9_1"},{"key":"10_CR12","doi-asserted-by":"publisher","unstructured":"Baran, I., Demaine, E.D., P\u01cetra\u015fcu, M.: Subquadratic algorithms for 3sum. Algorithmica 50(4), 584\u2013596 (2008). https:\/\/doi.org\/10.1007\/s00453-007-9036-3","DOI":"10.1007\/s00453-007-9036-3"},{"key":"10_CR13","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1142\/S0218195901000596","volume":"11","author":"G Barequet","year":"2001","unstructured":"Barequet, G., Har-Peled, S.: Polygon containment and translational min-hausdorff-distance between segment sets are 3sum-hard. Int. J. Comput. Geometry Appl. 11, 465\u2013474 (2001). https:\/\/doi.org\/10.1142\/S0218195901000596","journal-title":"Int. J. Comput. Geometry Appl."},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-20465-4_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"A Becker","year":"2011","unstructured":"Becker, A., Coron, J.-S., Joux, A.: Improved generic algorithms for hard knapsacks. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 364\u2013385. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20465-4_21"},{"key":"10_CR15","unstructured":"Berthet, Q., Rigollet, P.: Complexity theoretic lower bounds for sparse principal component detection. In: Annual Conference Computational Learning Theory (2013)"},{"issue":"4","key":"10_CR16","doi-asserted-by":"publisher","first-page":"1780","DOI":"10.1214\/13-AOS1127","volume":"41","author":"Q Berthet","year":"2013","unstructured":"Berthet, Q., Rigollet, P.: Optimal detection of sparse principal components in high dimension. Ann. Stat. 41(4), 1780\u20131815 (2013). https:\/\/doi.org\/10.1214\/13-AOS1127","journal-title":"Ann. Stat."},{"issue":"4","key":"10_CR17","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A Blum","year":"2003","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4), 506\u2013519 (2003). https:\/\/doi.org\/10.1145\/792538.792543","journal-title":"J. ACM"},{"key":"10_CR18","doi-asserted-by":"publisher","unstructured":"Boix-Adser\u00e0, E., Brennan, M.S., Bresler, G.: The average-case complexity of counting cliques in erd\u0151s-r\u00e9nyi hypergraphs. In: Zuckerman, D. (ed.) 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, 9\u201312 November 2019, pp. 1256\u20131280. IEEE Computer Society (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00078","DOI":"10.1109\/FOCS.2019.00078"},{"key":"10_CR19","unstructured":"Bouillaguet, C., Delaplace, C., Joux, A.: Algorithms for sparse random 3XOR: the low-density case (2021), https:\/\/hal.science\/hal-02306917. Working paper or preprint"},{"key":"10_CR20","doi-asserted-by":"publisher","unstructured":"Brakerski, Z., Stephens-Davidowitz, N., Vaikuntanathan, V.: On the hardness of average-case k-sum. In: Wootters, M., Sanit\u00e0, L. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), 16\u201318 August 2021. LIPIcs, vol.\u00a0207, pp. 29:1\u201329:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2021.29","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2021.29"},{"key":"10_CR21","doi-asserted-by":"publisher","unstructured":"Bringmann, K.: A near-linear pseudopolynomial time algorithm for subset sum. In: Klein, P.N. (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, 16\u201319 January 2017, pp. 1073\u20131084. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.69","DOI":"10.1137\/1.9781611974782.69"},{"key":"10_CR22","doi-asserted-by":"publisher","unstructured":"Brzuska, C., Couteau, G.: On building fine-grained one-way functions from strong average-case hardness. In: Dunkelman, O., Dziembowski, S. (eds.) Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, 30 May\u20133 June 2022, Proceedings, Part II. LNCS, vol. 13276, pp. 584\u2013613. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-031-07085-3_20","DOI":"10.1007\/978-3-031-07085-3_20"},{"key":"10_CR23","doi-asserted-by":"publisher","unstructured":"Carmosino, M.L., Gao, J., Impagliazzo, R., Mihajlin, I., Paturi, R., Schneider, S.: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS 2016, pp. 261-270. Association for Computing Machinery, New York (2016). https:\/\/doi.org\/10.1145\/2840728.2840746","DOI":"10.1145\/2840728.2840746"},{"key":"10_CR24","doi-asserted-by":"publisher","unstructured":"Chan, T.M.: More logarithmic-factor speedups for 3sum, (median, +)-convolution, and some geometric 3sum-hard problems. ACM Trans. Algor. 16(1), 7:1\u20137:23 (2020). https:\/\/doi.org\/10.1145\/3363541","DOI":"10.1145\/3363541"},{"key":"10_CR25","doi-asserted-by":"publisher","unstructured":"Chung, E., Larsen, K.G.: Stronger 3sum-indexing lower bounds. In: Bansal, N., Nagarajan, V. (eds.) Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, 22\u201325 January 2023, pp. 444\u2013455. SIAM (2023). https:\/\/doi.org\/10.1137\/1.9781611977554.ch19","DOI":"10.1137\/1.9781611977554.ch19"},{"key":"10_CR26","doi-asserted-by":"publisher","unstructured":"Dalirrooyfard, M., Lincoln, A., Williams, V.V.: New techniques for proving fine-grained average-case hardness. In: Irani, S. (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, 16\u201319 November 2020, pp. 774\u2013785. IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00077","DOI":"10.1109\/FOCS46700.2020.00077"},{"key":"10_CR27","doi-asserted-by":"publisher","unstructured":"Dam, E.R.V., Koolen, J.H., Tanaka, H.: Distance-regular graphs. Electron. J. Comb. 1000 (2016). https:\/\/doi.org\/10.37236\/4925","DOI":"10.37236\/4925"},{"key":"10_CR28","doi-asserted-by":"publisher","unstructured":"Dietzfelbinger, M., Schlag, P., Walzer, S.: A subquadratic algorithm for 3xor. In: Potapov, I., Spirakis, P.G., Worrell, J. (eds.) 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Liverpool, UK, 27\u201331 August 2018. LIPIcs, vol.\u00a0117, pp. 59:1\u201359:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.59","DOI":"10.4230\/LIPIcs.MFCS.2018.59"},{"key":"10_CR29","doi-asserted-by":"publisher","unstructured":"Dinur, I.: An algorithmic framework for the generalized birthday problem. Des. Codes Cryptogr. 87(8), 1897\u20131926 (2019). https:\/\/doi.org\/10.1007\/s10623-018-00594-6","DOI":"10.1007\/s10623-018-00594-6"},{"key":"10_CR30","doi-asserted-by":"publisher","unstructured":"Dinur, I., Keller, N., Klein, O.: Fine-grained cryptanalysis: tight conditional bounds for dense k-sum and k-xor. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, 7\u201310 February 2022, pp. 80\u201391. IEEE (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00017","DOI":"10.1109\/FOCS52979.2021.00017"},{"key":"10_CR31","unstructured":"Erickson, J.: Lower bounds for linear satisfiability problems. In: Clarkson, K.L. (ed.) Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, USA, 22\u201324 January 1995, pp. 388\u2013395. ACM\/SIAM (1995). http:\/\/dl.acm.org\/citation.cfm?id=313651.313772"},{"key":"10_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/978-3-319-63715-0_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"A Esser","year":"2017","unstructured":"Esser, A., K\u00fcbler, R., May, A.: LPN decoded. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 486\u2013514. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63715-0_17"},{"key":"10_CR33","doi-asserted-by":"publisher","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of o(n2) problems in computational geometry. Comput. Geom. 5(3), 165\u2013185 (1995). https:\/\/doi.org\/10.1016\/0925-7721(95)00022-2. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0925772195000222","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"10_CR34","unstructured":"Gamarnik, D., Zadik, I.: The landscape of the planted clique problem: dense subgraphs and the overlap gap property. CoRR http:\/\/arxiv.org\/abs\/1904.07174 (2019)"},{"key":"10_CR35","doi-asserted-by":"publisher","unstructured":"Gold, O., Sharir, M.: Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy. In: Pruhs, K., Sohler, C. (eds.) 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a087, pp. 42:1\u201342:13. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.42. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/7836","DOI":"10.4230\/LIPIcs.ESA.2017.42"},{"key":"10_CR36","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 25\u201332 (1989)","DOI":"10.1145\/73007.73010"},{"key":"10_CR37","doi-asserted-by":"publisher","unstructured":"Goldreich, O., Rothblum, G.N.: Counting t-cliques: worst-case to average-case reductions and direct interactive proof systems. In: Thorup, M. (ed.) 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 7\u20139 October 2018, pp. 77\u201388. IEEE Computer Society (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00017","DOI":"10.1109\/FOCS.2018.00017"},{"key":"10_CR38","doi-asserted-by":"publisher","unstructured":"Golovnev, A., Guo, S., Horel, T., Park, S., Vaikuntanathan, V.: Data structures meet cryptography: 3sum with preprocessing. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, 22\u201326 June 2020, pp. 294\u2013307. ACM (2020). https:\/\/doi.org\/10.1145\/3357713.3384342","DOI":"10.1145\/3357713.3384342"},{"key":"10_CR39","doi-asserted-by":"publisher","unstructured":"Gr\u00f8nlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. J. ACM 65(4) (2018). https:\/\/doi.org\/10.1145\/3185378","DOI":"10.1145\/3185378"},{"key":"10_CR40","unstructured":"Gupte, A., Vaikuntanathan, V.: The fine-grained hardness of sparse linear regression. CoRR (2021). https:\/\/arxiv.org\/abs\/2106.03131"},{"key":"10_CR41","doi-asserted-by":"crossref","unstructured":"Hirahara, S., Shimizu, N.: Hardness self-amplification: simplified, optimized, and unified. Electron. Colloquium Comput. Complex. TR23-026 (2023). https:\/\/eccc.weizmann.ac.il\/report\/2023\/026","DOI":"10.1145\/3564246.3585189"},{"issue":"2","key":"10_CR42","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM 21(2), 277\u2013292 (1974). https:\/\/doi.org\/10.1145\/321812.321823","journal-title":"J. ACM"},{"key":"10_CR43","doi-asserted-by":"publisher","unstructured":"H\u00c5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999). https:\/\/doi.org\/10.1137\/S0097539793244708","DOI":"10.1137\/S0097539793244708"},{"key":"10_CR44","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: A personal view of average-case complexity. In: Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, pp. 134\u2013147. IEEE (1995)","DOI":"10.1109\/SCT.1995.514853"},{"issue":"4","key":"10_CR45","doi-asserted-by":"publisher","first-page":"1637","DOI":"10.1137\/080734030","volume":"39","author":"R Impagliazzo","year":"2010","unstructured":"Impagliazzo, R., Jaiswal, R., Kabanets, V., Wigderson, A.: Uniform direct product theorems: simplified, optimized, and derandomized. SIAM J. Comput. 39(4), 1637\u20131665 (2010). https:\/\/doi.org\/10.1137\/080734030","journal-title":"SIAM J. Comput."},{"key":"10_CR46","doi-asserted-by":"publisher","unstructured":"Impagliazzo, R., Naor, M.: Efficient cryptographic schemes provably as secure as subset sum. In: 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October\u20131 November 1989, pp. 236\u2013241. IEEE Computer Society (1989). https:\/\/doi.org\/10.1109\/SFCS.1989.63484","DOI":"10.1109\/SFCS.1989.63484"},{"issue":"4","key":"10_CR47","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1002\/rsa.3240030402","volume":"3","author":"M Jerrum","year":"1992","unstructured":"Jerrum, M.: Large cliques elude the metropolis process. Rand. Struct. Algor. 3(4), 347\u2013360 (1992). https:\/\/doi.org\/10.1002\/rsa.3240030402","journal-title":"Rand. Struct. Algor."},{"key":"10_CR48","doi-asserted-by":"publisher","unstructured":"Jin, C., Wu, H.: A simple near-linear pseudopolynomial time randomized algorithm for subset sum. In: Fineman, J.T., Mitzenmacher, M. (eds.) 2nd Symposium on Simplicity in Algorithms, SOSA 2019, San Diego, CA, USA, 8\u20139 January 2019. OASIcs, vol.\u00a069, pp. 17:1\u201317:6. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2019.17","DOI":"10.4230\/OASIcs.SOSA.2019.17"},{"issue":"3","key":"10_CR49","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1023\/A:1008374125234","volume":"20","author":"A Juels","year":"2000","unstructured":"Juels, A., Peinado, M.: Hiding cliques for cryptographic security. Des. Codes Crypt. 20(3), 269\u2013280 (2000)","journal-title":"Des. Codes Crypt."},{"issue":"3","key":"10_CR50","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00145-010-9061-2","volume":"23","author":"J Katz","year":"2010","unstructured":"Katz, J., Shin, J.S., Smith, A.: Parallel and concurrent security of the HB and HB+ protocols. J. Cryptol. 23(3), 402\u2013421 (2010)","journal-title":"J. Cryptol."},{"key":"10_CR51","doi-asserted-by":"crossref","unstructured":"Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3sum conjecture. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 1272\u20131287. Society for Industrial and Applied Mathematics, USA (2016)","DOI":"10.1137\/1.9781611974331.ch89"},{"key":"10_CR52","unstructured":"Kopelowitz, T., Porat, E.: The strong 3sum-indexing conjecture is false. CoRR http:\/\/arxiv.org\/abs\/1907.11206 (2019)"},{"issue":"1","key":"10_CR53","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"JC Lagarias","year":"1985","unstructured":"Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. J. ACM 32(1), 229\u2013246 (1985). https:\/\/doi.org\/10.1145\/2455.2461","journal-title":"J. ACM"},{"key":"10_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/978-3-030-26954-8_20","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"R LaVigne","year":"2019","unstructured":"LaVigne, R., Lincoln, A., Vassilevska Williams, V.: Public-key cryptography in the fine-grained setting. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 605\u2013635. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26954-8_20"},{"key":"10_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-030-26951-7_8","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"G Leurent","year":"2019","unstructured":"Leurent, G., Sibleyras, F.: Low-memory attacks against two-round even-mansour using the 3-XOR problem. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 210\u2013235. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26951-7_8"},{"key":"10_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-19074-2_21","volume-title":"Topics in Cryptology \u2013 CT-RSA 2011","author":"R Lindner","year":"2011","unstructured":"Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319\u2013339. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19074-2_21"},{"key":"10_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/978-3-642-11799-2_23","volume-title":"Theory of Cryptography","author":"V Lyubashevsky","year":"2010","unstructured":"Lyubashevsky, V., Palacio, A., Segev, G.: Public-key cryptographic primitives provably as secure as subset sum. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 382\u2013400. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11799-2_23"},{"key":"10_CR58","doi-asserted-by":"publisher","unstructured":"Minder, L., Sinclair, A.: The extended k-tree algorithm. J. Cryptol. 25(2), 349\u2013382 (2012). https:\/\/doi.org\/10.1007\/s00145-011-9097-y","DOI":"10.1007\/s00145-011-9097-y"},{"key":"10_CR59","unstructured":"Nandi, M.: Revisiting security claims of XLS and COPA. IACR Cryptol. ePrint Arch., p.\u00a0444 (2015). http:\/\/eprint.iacr.org\/2015\/444"},{"key":"10_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1007\/978-3-662-48800-3_28","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2015","author":"I Nikoli\u0107","year":"2015","unstructured":"Nikoli\u0107, I., Sasaki, Yu.: Refinements of the k-tree algorithm for the generalized birthday problem. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 683\u2013703. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48800-3_28"},{"key":"10_CR61","doi-asserted-by":"publisher","unstructured":"Patrascu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC 2010, pp. 603\u2013610. Association for Computing Machinery, New York (2010). https:\/\/doi.org\/10.1145\/1806689.1806772","DOI":"10.1145\/1806689.1806772"},{"key":"10_CR62","doi-asserted-by":"publisher","unstructured":"Patrascu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Charikar, M. (ed.) Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, 17\u201319 January 2010, pp. 1065\u20131075. SIAM (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.86","DOI":"10.1137\/1.9781611973075.86"},{"key":"10_CR63","unstructured":"Pettie, S.: Higher Lower Bounds from the 3SUM Conjecture, talk at the Computational Complexity of Low-Polynomial Time Problems workshop at the Simons Institute (2015). https:\/\/simons.berkeley.edu\/talks\/higher-lower-bounds-3sum-conjecture"},{"key":"10_CR64","doi-asserted-by":"publisher","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009). https:\/\/doi.org\/10.1145\/1568318.1568324","DOI":"10.1145\/1568318.1568324"},{"key":"10_CR65","doi-asserted-by":"publisher","unstructured":"Soss, M., Erickson, J., Overmars, M.: Preprocessing chains for fast dihedral rotations is hard or even impossible. Comput. Geom. 26(3), 235\u2013246 (2003). https:\/\/doi.org\/10.1016\/S0925-7721(02)00156-6. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0925772102001566","DOI":"10.1016\/S0925-7721(02)00156-6"},{"key":"10_CR66","unstructured":"Trevisan, L.: Some applications of coding theory in computational complexity. arXiv preprint cs\/0409044 (2004)"},{"key":"10_CR67","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-45708-9_19","volume-title":"Advances in Cryptology \u2014 CRYPTO 2002","author":"D Wagner","year":"2002","unstructured":"Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288\u2013304. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45708-9_19"},{"key":"10_CR68","unstructured":"Williams, V.V.: On some fine-grained questions in algorithms and complexity. In: Proceedings of the ICM, vol.\u00a03, pp. 3431\u20133472. World Scientific (2018)"},{"key":"10_CR69","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-662-53018-4_9","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"Yu Yu","year":"2016","unstructured":"Yu, Yu., Zhang, J.: Cryptography with auxiliary input and trapdoor from constant-noise LPN. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 214\u2013243. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53018-4_9"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2024"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-68379-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T19:24:16Z","timestamp":1732649056000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-68379-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031683787","9783031683794"],"references-count":69,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-68379-4_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"16 August 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"44","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}