{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:27Z","timestamp":1781028267831,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":46,"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":[{"name":"European Research Council","award":["835152"],"award-info":[{"award-number":["835152"]}]},{"name":"Israel Science Foundation","award":["1488\/22"],"award-info":[{"award-number":["1488\/22"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800803","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"886-897","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic Hardness of Approximation of Unique-SVP and GapSVP in \u2113<i><sub>p<\/sub><\/i> Norms for <i>p>2<\/i>"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-0596-080X","authenticated-orcid":false,"given":"Yahli","family":"Hecht","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5022-7727","authenticated-orcid":false,"given":"Muli","family":"Safra","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"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.1016\/j.ipl.2016.05.003"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276705"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258604"},{"key":"e_1_3_2_1_4_1","unstructured":"Mikl\u00f3s Ajtai and Cynthia Dwork. 2007. The first and fourth public-key cryptosystems with worst-case\/average-case equivalence. In Electronic colloquium on computational complexity (ECCC). 14."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30589-4_9"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.36"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2023.37"},{"key":"e_1_3_2_1_9_1","unstructured":"Vijay Bhattiprolu Venkatesan Guruswami Euiwoong Lee and Xuandi Ren. 2025. Inapproximability of Finding Sparse Vectors in Codes Subspaces and Lattices. arxiv:2410.02636. arxiv:2410.02636"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00290-0"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301265"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00037-011-0014-4"},{"key":"e_1_3_2_1_13_1","volume-title":"TR17-094","author":"Dinur Irit","year":"2017","unstructured":"Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. 2017. On Non-Optimally Expanding Sets in Grassmann Graphs. Electron. Colloquium Comput. Complex., TR17-094 (2017), eccc:TR17-094. https:\/\/eccc.weizmann.ac.il\/report\/2017\/094"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188804"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","unstructured":"I. Dinur Guy Kindler R. Raz and S. Safra. 2003. Approximating CVP to Within Almost-Polynomial Factors is NP-Hard. Combinatorica 23 (2003) 04 205\u2013243. https:\/\/doi.org\/10.1007\/s00493-003-0019-y 10.1007\/s00493-003-0019-y","DOI":"10.1007\/s00493-003-0019-y"},{"key":"e_1_3_2_1_16_1","volume-title":"Proc. 39th IEEE Symposium on Foundations of Computer Science.","author":"Dinur I.","unstructured":"I. Dinur, G. Kindler, and S. Safra. 1998. Approximating CVP to within almost-polynomial factors is NP-hard. In Proc. 39th IEEE Symposium on Foundations of Computer Science."},{"key":"e_1_3_2_1_17_1","volume-title":"TR96-056","author":"Goldreich Oded","year":"1996","unstructured":"Oded Goldreich, Shafi Goldwasser, and Shai Halevi. 1996. Public-Key Cryptosystems from Lattice Reduction Problems. Electron. Colloquium Comput. Complex., TR96-056 (1996), eccc:TR96-056. https:\/\/eccc.weizmann.ac.il\/eccc-reports\/1996\/TR96-056\/index.html"},{"key":"e_1_3_2_1_18_1","volume-title":"Paper 2025\/2181. https:\/\/eprint.iacr.org\/2025\/2181","author":"Hair Isaac M","unstructured":"Isaac M Hair and Amit Sahai. 2025. SVP_p is Deterministically NP-Hard for all p > 2, Even to Approximate Within a Factor of 2^log ^1-\u03b5 n. Cryptology ePrint Archive, Paper 2025\/2181. https:\/\/eprint.iacr.org\/2025\/2181"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2012.V008A023"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.48550\/arxiv.1806.04087"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Yahli Hecht and Muli Safra. 2025. Deterministic Hardness of Approximation of Unique-SVP and GapSVP in \u2113 _p norms for p>2. Oct. arxiv:2510.16991. https:\/\/doi.org\/10.48550\/ARXIV.2510.16991 10.48550\/ARXIV.2510.16991","DOI":"10.48550\/ARXIV.2510.16991"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFB0054868"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1360\/ssi-2024-0145"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/23M1571022"},{"key":"e_1_3_2_1_25_1","unstructured":"Than Quang Khoat and Nguyen Hong Tan. 2008. Unique shortest vector problem for max norm is NP-hard. Cryptology ePrint Archive."},{"key":"e_1_3_2_1_26_1","volume-title":"Proc. 44th IEEE Symposium on Foundations of Computer Science.","author":"Khot S.","year":"2003","unstructured":"S. Khot. 2003. Hardness of approximating the shortest vector problem in high L_p norms. In Proc. 44th IEEE Symposium on Foundations of Computer Science."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089027"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055432"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2023.198.1.1"},{"key":"e_1_3_2_1_30_1","volume-title":"On the unique shortest lattice vector problem. Theoretical computer science, 255, 1-2","author":"Ravi Kumar S","year":"2001","unstructured":"S Ravi Kumar and D Sivakumar. 2001. On the unique shortest lattice vector problem. Theoretical computer science, 255, 1-2 (2001), 641\u2013648."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_41"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_34"},{"key":"e_1_3_2_1_33_1","unstructured":"D. Micciancio. 1998. On the hardness of the shortest vector problem. PhD Thesis MIT."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700373039"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a022"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3568031"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00022"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649606"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0278-0"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000074"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039490"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_3_2_1_44_1","unstructured":"Noah Stephens-Davidowitz. 2015. Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one. arXiv preprint arXiv:1512.04138."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22196"},{"key":"e_1_3_2_1_46_1","unstructured":"Boas P van Emde. 1981. Another NP-complete partition problem and the complexity of computing short vectors in lattices. TR."}],"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.3800803","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:55:02Z","timestamp":1781027702000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800803"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":46,"alternative-id":["10.1145\/3798129.3800803","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800803","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"}}]}}