{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,8]],"date-time":"2022-08-08T01:05:16Z","timestamp":1659920716159},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2005,9]]},"abstract":"\n Let\n p<\/jats:italic>\n > 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 \n p<\/jats:italic>\n <\/jats:sub>\n norm within a constant factor. Under the stronger assumption NP \u2288 RTIME(2\n \n poly<\/jats:italic>\n (log\n n<\/jats:italic>\n )\n <\/jats:sup>\n ), we show that there is no polynomial-time algorithm with approximation ratio 2\n \n (log\n n<\/jats:italic>\n )\n 1\/2\u2212\u03f5<\/jats:sup>\n <\/jats:sup>\n where\n n<\/jats:italic>\n is the dimension of the lattice and \u03f5 > 0 is an arbitrarily small constant.We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves\n 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 behave well<\/jats:italic>\n under the\n 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 \n (log\n n<\/jats:italic>\n )\n 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","source":"Crossref","is-referenced-by-count":72,"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"}]}],"member":"320","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\/pdf\/10.1145\/1089023.1089027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T00:56:11Z","timestamp":1613609771000},"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":"http:\/\/dx.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":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2005,9]]}}}