{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:50:18Z","timestamp":1781077818700,"version":"3.54.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2005,9,1]],"date-time":"2005-09-01T00:00:00Z","timestamp":1125532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2005,9]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>p<\/jats:italic>\n            &gt; 1 be any fixed real. We show that assuming NP \u2288 RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in \u2113\n            <jats:sub>\n              <jats:italic>p<\/jats:italic>\n            <\/jats:sub>\n            norm within a constant factor. Under the stronger assumption NP \u2288 RTIME(2\n            <jats:sup>\n              <jats:italic>poly<\/jats:italic>\n              (log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            ), we show that there is no polynomial-time algorithm with approximation ratio 2\n            <jats:sup>\n              (log\n              <jats:italic>n<\/jats:italic>\n              )\n              <jats:sup>1\/2\u2212\u03f5<\/jats:sup>\n            <\/jats:sup>\n            where\n            <jats:italic>n<\/jats:italic>\n            is the dimension of the lattice and \u03f5 &gt; 0 is an arbitrarily small constant.We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves\n            <jats:italic>some<\/jats:italic>\n            constant factor hardness. The reduction is based on BCH Codes. Its advantage is that the SVP instances produced by the reduction\n            <jats:italic>behave well<\/jats:italic>\n            under the\n            <jats:italic>augmented tensor product<\/jats:italic>\n            , a new variant of tensor product that we introduce. This enables us to boost the hardness factor to 2\n            <jats:sup>\n              (log\n              <jats:italic>n<\/jats:italic>\n              )\n              <jats:sup>1\/2-\u03f5<\/jats:sup>\n            <\/jats:sup>\n            .\n          <\/jats:p>","DOI":"10.1145\/1089023.1089027","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"789-808","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":112,"title":["Hardness of approximating the shortest vector problem in lattices"],"prefix":"10.1145","volume":"52","author":[{"given":"Subhash","family":"Khot","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, Georgia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2005,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 45th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Aharonov D.","year":"2004"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 28th ACM Symposium on the Theory of Computing. ACM","author":"Ajtai M.","year":"1996"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 30th ACM Symposium on the Theory of Computing. ACM","author":"Ajtai M.","year":"1998"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 29th ACM Symposium on the Theory of Computing. ACM","author":"Ajtai M."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 33rd ACM Symposium on the Theory of Computing. ACM","author":"Ajtai M."},{"key":"e_1_2_1_6_1","unstructured":"Alon N. Spencer J. and Erdos P. 1991. The Probabilistic Method. Wiley-Interscience Series.  Alon N. Spencer J. and Erdos P. 1991. The Probabilistic Method. Wiley-Interscience Series."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1007\/BF01445125","article-title":"New bounds in some transference theorems in the geometry of numbers","volume":"296","author":"Banaszczyk W.","year":"1993","journal-title":"Math. Ann."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00216-0"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 38th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Cai J."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1649"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0019-y"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Dinur I."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 40th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Dumer I."},{"key":"e_1_2_1_15_1","volume-title":"Clarke","author":"Gauss C.","year":"1801"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1686"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00083-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF02122554","article-title":"Dual vectors and lower bounds for the nearest lattice point problem","volume":"8","author":"Hastad J.","year":"1988","journal-title":"Combinatorica"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 15th ACM Symposium on Theory of Computing. ACM","author":"Kannan R.","year":"1983"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 44th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Khot S.","year":"2003"},{"key":"e_1_2_1_22_1","first-page":"3","article-title":"Complexity of SVP---A reader's digest. Complexity Theory Column, L. Hemaspaandra","volume":"32","author":"Kumar R.","year":"2001","journal-title":"Ed. SIGACT News"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF02128669","article-title":"Korkine--Zolotarev bases and successive minima of a lattice and its reciprocal lattice","volume":"10","author":"Lagarias J.","year":"1990","journal-title":"Combinatorica"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.2461"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0022-0000(85)90013-3","article-title":"Solvability of radicals is in polynomial time","volume":"30","author":"Landau S.","year":"1985","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra A.","year":"1982","journal-title":"Math. Ann."},{"key":"e_1_2_1_27_1","first-page":"81","article-title":"Integer programming with a fixed number of variables","author":"Lenstra H.","year":"1981","journal-title":"Tech. Report"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700373039"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Micciancio D. and Goldwasser S. 2002. Complexity of Lattice Problems A Cryptographic Perspective. Kluwer Academic Publishers.   Micciancio D. and Goldwasser S. 2002. Complexity of Lattice Problems A Cryptographic Perspective. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-0897-7"},{"key":"e_1_2_1_30_1","unstructured":"Minkowski H. 1910. Geometrie der zahlen. Tuebner.  Minkowski H. 1910. Geometrie der zahlen. Tuebner."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 35th ACM Symposium on the Theory of Computing. ACM","author":"Regev O.","year":"2003"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90064-8"},{"key":"e_1_2_1_33_1","first-page":"81","article-title":"Another NP-complete problem and the complexity of computing short vectors in a lattice","author":"van Emde Boas P.","year":"1981","journal-title":"Tech. Report"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089023.1089027","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1089023.1089027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:22Z","timestamp":1750262902000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089023.1089027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2005,9]]}},"alternative-id":["10.1145\/1089023.1089027"],"URL":"https:\/\/doi.org\/10.1145\/1089023.1089027","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,9]]},"assertion":[{"value":"2005-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}