{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T01:10:13Z","timestamp":1613610613884},"reference-count":30,"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":"We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of \u221an lie in NP intersect coNP. The result (almost) subsumes the three mutually-incomparable previous results regarding these lattice problems: Banaszczyk [1993], Goldreich and Goldwasser [2000], and Aharonov and Regev [2003]. Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier series over the lattice. This technique might be useful elsewhere---we demonstrate this by giving a simple and efficient algorithm for one other lattice problem (CVPP) improving on a previous result of Regev[2003]. An interesting fact is that our result emerged from a \u201cdequantization\u201d of our previous quantum result in Aharonov and Regev [2003]. This route to proving purely classical results might be beneficial elsewhere.<\/jats:p>","DOI":"10.1145\/1089023.1089025","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"749-765","source":"Crossref","is-referenced-by-count":59,"title":["Lattice problems in NP \u2229 coNP"],"prefix":"10.1145","volume":"52","author":[{"given":"Dorit","family":"Aharonov","sequence":"first","affiliation":[{"name":"The Hebrew University, Jerusalem, Israel"}]},{"given":"Oded","family":"Regev","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","author":"Aaronson S.","year":"2004","volume-title":"Proceedings of the 36th ACM Symposium on Theory of Computing (STOC). ACM"},{"key":"e_1_2_1_2_1","author":"Aharonov D.","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif., 210--219"},{"key":"e_1_2_1_3_1","author":"Ajtai M.","year":"1996","volume-title":"Proceedings of the 28th ACM Symposium on Theory of Computing (STOC). ACM"},{"key":"e_1_2_1_4_1","author":"Ajtai M.","year":"1998","volume-title":"Proceedings of the 30th ACM Symposium on Theory of Computing (STOC). ACM"},{"key":"e_1_2_1_5_1","author":"Ajtai M.","volume-title":"Proceedings of the 29th ACM Symposium on Theory of Computing (STOC). ACM"},{"key":"e_1_2_1_6_1","author":"Ajtai M.","volume-title":"Proceedings of the 33rd ACM Symposium on Theory of Computing. ACM"},{"key":"e_1_2_1_7_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_8_1","DOI":"10.1137\/0221003","doi-asserted-by":"publisher"},{"key":"e_1_2_1_9_1","DOI":"10.1016\/S0020-0190(00)00123-X","doi-asserted-by":"publisher"},{"key":"e_1_2_1_10_1","DOI":"10.1007\/s00493-003-0019-y","doi-asserted-by":"publisher"},{"key":"e_1_2_1_11_1","unstructured":"Feige U. and Micciancio D. 2002. The inapproximability of lattice and coding problems with preprocessing. In Computational Complexity. IEEE Computer Society Press Los Alamitos Calif. 44--52. Feige U. and Micciancio D. 2002. The inapproximability of lattice and coding problems with preprocessing. In Computational Complexity. IEEE Computer Society Press Los Alamitos Calif. 44--52."},{"key":"e_1_2_1_12_1","unstructured":"Gauss C. F. 1801. Disquisitiones Arithmeticae. Gerh. Fleischer Iun. Gauss C. F. 1801. Disquisitiones Arithmeticae. Gerh. Fleischer Iun.","DOI":"10.5479\/sil.324926.39088000932822","doi-asserted-by":"crossref"},{"key":"e_1_2_1_13_1","unstructured":"Goldreich O. 2003. A comment available online at http:\/\/www.wisdom.weizmann.ac.il\/~oded\/p_lp.html. Goldreich O. 2003. A comment available online at http:\/\/www.wisdom.weizmann.ac.il\/~oded\/p_lp.html."},{"key":"e_1_2_1_14_1","DOI":"10.1006\/jcss.1999.1686","doi-asserted-by":"publisher"},{"key":"e_1_2_1_15_1","DOI":"10.1016\/S0020-0190(99)00083-6","doi-asserted-by":"publisher"},{"key":"e_1_2_1_16_1","DOI":"10.1137\/0218059","doi-asserted-by":"publisher"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding W.","year":"1963","journal-title":"J. Amer. Stat. Assoc."},{"key":"e_1_2_1_18_1","author":"Kannan R.","year":"1983","volume-title":"Proceedings of the 15th ACM Symposium on Theory of Computing (STOC). ACM"},{"key":"e_1_2_1_19_1","author":"Kerenidis I.","year":"2003","volume-title":"Proceedings of the 35th ACM Symposium on Theory of Computing (STOC). ACM"},{"key":"e_1_2_1_20_1","author":"Khot S.","year":"2004","volume-title":"Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif., 126--135"},{"key":"e_1_2_1_21_1","DOI":"10.1137\/0222080","doi-asserted-by":"publisher"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF02128669","article-title":"Korkin--Zolotarev bases and successive minima of a lattice and its reciprocal lattice","volume":"10","author":"Lagarias J. C.","year":"1990","journal-title":"Combinatorica"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra A. K.","year":"1982","journal-title":"Math. Ann."},{"key":"e_1_2_1_24_1","DOI":"10.1137\/S0097539700373039","doi-asserted-by":"publisher"},{"key":"e_1_2_1_25_1","author":"Micciancio D.","volume":"671","volume-title":"The Kluwer International Series in Engineering and Computer Science"},{"key":"e_1_2_1_26_1","author":"Regev O.","year":"2003","volume-title":"Proceedings of the of 18th IEEE Annual Conference on Computational Complexity (CCC). IEEE Computer Society Press, Los Alamitos, Calif., 363--370"},{"key":"e_1_2_1_27_1","DOI":"10.1016\/0304-3975(87)90064-8","doi-asserted-by":"publisher"},{"key":"e_1_2_1_28_1","author":"Schnorr C.-P.","volume":"547","year":"1991","volume-title":"Proceedings of the of Eurocrypt '91"},{"key":"e_1_2_1_29_1","unstructured":"Stein E. M. and Weiss G. 1971. Introduction to Fourier analysis on Euclidean spaces. Princeton University Press Princeton N.J. (Princeton Mathematical Series No. 32.) Stein E. M. and Weiss G. 1971. Introduction to Fourier analysis on Euclidean spaces. Princeton University Press Princeton N.J. (Princeton Mathematical Series No. 32.)"},{"key":"e_1_2_1_31_1","unstructured":"\u0160tefankovi\u010d D. 2002. Fourier transforms in computer science. Master's Thesis University of Chicago Department of Computer Science TR-2002-03. \u0160tefankovi\u010d D. 2002. Fourier transforms in computer science. Master's Thesis University of Chicago Department of Computer Science TR-2002-03."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1089023.1089025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T00:55:18Z","timestamp":1613609718000},"score":1.0,"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9]]},"references-count":30,"journal-issue":{"published-print":{"date-parts":[[2005,9]]},"issue":"5"},"alternative-id":["10.1145\/1089023.1089025"],"URL":"http:\/\/dx.doi.org\/10.1145\/1089023.1089025","relation":{"cites":[]},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Control and Systems Engineering","Hardware and Architecture","Software","Artificial Intelligence","Information Systems"]}}