{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:00Z","timestamp":1781031420767,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2333935"],"award-info":[{"award-number":["2333935"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800879","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1716-1727","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["SVP<i><sub>p<\/sub><\/i> Is Deterministically NP-Hard for All p > 2, Even to Approximate within a Factor of <i>2<sup>log<sup>1-\u03b5<\/sup>n<\/sup><\/i>"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6992-4488","authenticated-orcid":false,"given":"Isaac M.","family":"Hair","sequence":"first","affiliation":[{"name":"University of California at Santa Barbara, Santa Barbara, USA"},{"name":"University of California at Los Angeles, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2216-9600","authenticated-orcid":false,"given":"Amit","family":"Sahai","sequence":"additional","affiliation":[{"name":"University of California at Los Angeles, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.145"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188840"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276705"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873162"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3586165.3586172"},{"key":"e_1_3_2_1_8_1","unstructured":"Huck Bennett and Chris Peikert. 2022. Hardness of the (approximate) shortest vector problem: A simple proof via Reed-Solomon codes. arXiv preprint arXiv:2202.07736."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Vijay Bhattiprolu Venkatesan Guruswami Euiwoong Lee and Xuandi Ren. 2024. Inapproximability of Finding Sparse Vectors in Codes Subspaces and Lattices. arXiv preprint arXiv:2410.02636.","DOI":"10.1109\/FOCS63196.2025.00068"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.045"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings. Thirteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference)(Cat. No. 98CB36247)","author":"Cai Jin-Yi","year":"1998","unstructured":"Jin-Yi Cai and Ajay Nerurkar. 1998. Approximating the SVP to within a factor (1-1\/dim\/sup\/spl epsiv\/\/) is NP-hard under randomized conditions. In Proceedings. Thirteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference)(Cat. No. 98CB36247). 46\u201355."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.29612"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00290-0"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301265"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746630"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.09.006"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.21245"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250859"},{"key":"e_1_3_2_1_21_1","volume-title":"34th International Symposium on Algorithms and Computation (ISAAC","author":"Hirahara Shuichi","year":"2023","unstructured":"Shuichi Hirahara and Dana Moshkovitz. 2023. Regularization of Low Error PCPs and an Application to MCSP. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). 39\u20131."},{"key":"e_1_3_2_1_22_1","volume-title":"Ueber einen mittelwerthabsatz. Nachrichten von der K\u00f6nigl","author":"H\u00f6lder Otto","year":"1889","unstructured":"Otto H\u00f6lder. 1889. Ueber einen mittelwerthabsatz. Nachrichten von der K\u00f6nigl. Gesellschaft der Wissenschaften und der Georg-Augusts-Universit\u00e4t zu G\u00f6ttingen, 1889 (1889), 38\u201347."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511840371"},{"key":"e_1_3_2_1_24_1","volume-title":"Minkowski\u2019s convex body theorem and integer programming. Mathematics of operations research, 12, 3","author":"Kannan Ravi","year":"1987","unstructured":"Ravi Kannan. 1987. Minkowski\u2019s convex body theorem and integer programming. Mathematics of operations research, 12, 3 (1987), 415\u2013440."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946339"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089027"},{"key":"e_1_3_2_1_27_1","volume-title":"Factoring polynomials with rational coefficients. Math. ann, 261, 4","author":"Lenstra AK","year":"1982","unstructured":"AK Lenstra, HW Lenstra, and L Lov\u00e1sz. 1982. Factoring polynomials with rational coefficients. Math. ann, 261, 4 (1982), 515\u2013534."},{"key":"e_1_3_2_1_28_1","volume-title":"Integer programming with a fixed number of variables. Mathematics of operations research, 8, 4","author":"Lenstra Hendrik W","year":"1983","unstructured":"Hendrik W Lenstra Jr. 1983. Integer programming with a fixed number of variables. Mathematics of operations research, 8, 4 (1983), 538\u2013548."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700373039"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a022"},{"key":"e_1_3_2_1_31_1","series-title":"SIAM journal on computing, 37, 1","volume-title":"Worst-case to average-case reductions based on Gaussian measures","author":"Micciancio Daniele","year":"2007","unstructured":"Daniele Micciancio and Oded Regev. 2007. Worst-case to average-case reductions based on Gaussian measures. SIAM journal on computing, 37, 1 (2007), 267\u2013302."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_24"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754402"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.09.002"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44670-2_12"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62233"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Chris Peikert et al. 2016. A decade of lattice cryptography. Foundations and trends\u00ae in theoretical computer science 10 4 (2016) 283\u2013424.","DOI":"10.1561\/0400000074"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132581"},{"key":"e_1_3_2_1_40_1","volume-title":"Theory of linear and integer programming","author":"Schrijver Alexander","unstructured":"Alexander Schrijver. 1998. Theory of linear and integer programming. John Wiley & Sons."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Salil P Vadhan et al. 2012. Pseudorandomness. Foundations and Trends\u00ae in Theoretical Computer Science 7 1\u20133 (2012) 1\u2013336.","DOI":"10.1561\/0400000010"},{"key":"e_1_3_2_1_42_1","volume-title":"Department of Mathmatics","author":"van Emde Boas Peter","unstructured":"Peter van Emde Boas. 1981. Another NP-complete problem and the complexity of computing short vectors in a lattice. Tecnical Report, Department of Mathmatics, University of Amsterdam."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139045520"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800879","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800879","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:59:19Z","timestamp":1781027959000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800879"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":43,"alternative-id":["10.1145\/3798129.3800879","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800879","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}