{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T23:35:36Z","timestamp":1648510536500},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,3,28]],"date-time":"2013-03-28T00:00:00Z","timestamp":1364428800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sci. China Inf. Sci."],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s11432-013-4795-8","type":"journal-article","created":{"date-parts":[[2013,3,14]],"date-time":"2013-03-14T16:08:24Z","timestamp":1363277304000},"page":"1-7","source":"Crossref","is-referenced-by-count":1,"title":["A polynomial time algorithm for GapCVPP in l 1 norm"],"prefix":"10.1007","volume":"57","author":[{"given":"ChengLiang","family":"Tian","sequence":"first","affiliation":[]},{"given":"LiDong","family":"Han","sequence":"additional","affiliation":[]},{"given":"GuangWu","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,28]]},"reference":[{"key":"4795_CR1","doi-asserted-by":"crossref","DOI":"10.5479\/sil.324926.39088000932822","volume-title":"Disquisitiones Arithmeticae","author":"C F Gauss","year":"1801","unstructured":"Gauss C F. Disquisitiones Arithmeticae. Leipzig: Gerh Fleischer Iun, 1801"},{"key":"4795_CR2","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/BF01457454","volume":"261","author":"A K Lenstra","year":"1982","unstructured":"Lenstra A K, Lenstra H W, Lov\u00e1sz L. Factoring polynomials with rational coefficients. Math Ann, 1982, 261: 513\u2013534","journal-title":"Math Ann"},{"key":"4795_CR3","first-page":"193","volume-title":"Proceedings of the 15th Annual ACM Symposium on Theory of Computing","author":"R Kannan","year":"1983","unstructured":"Kannan R. Improved algorithms for integer programming and related lattice problems. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing. New York: ACM, 1983. 193\u2013206"},{"key":"4795_CR4","first-page":"145","volume-title":"Proceedings of the 23rd Annual Symposium on Foundations of Computer Science","author":"A Shamir","year":"1982","unstructured":"Shamir A. A polynomial time algorithm for breading the basic Merkel-Hellman cryptosystem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. Washington DC: IEEE, 1982. 145\u2013152"},{"key":"4795_CR5","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1090\/psapm\/042\/1095552","volume":"42","author":"A M Odlyzko","year":"1989","unstructured":"Odlyzko A M. The rise and fall of knapsack cryptosystems. In: Pomerance C, ed. Cryptology and Computational Number Theory. Proceedings of Symposia in Applied Mathematics. Boulder: AMS, 1989. 42: 75\u201388","journal-title":"Cryptology and Computational Number Theory. Proceedings of Symposia in Applied Mathematics"},{"key":"4795_CR6","first-page":"99","volume-title":"Proceedings of the 28th Annual ACM Symposium on Theory of Computing","author":"M Ajtai","year":"1996","unstructured":"Ajtai M. Generating hard instances of lattice problems (extended abstract). In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. New York: ACM, 1996. 99\u2013108"},{"key":"4795_CR7","doi-asserted-by":"crossref","first-page":"1212","DOI":"10.1109\/18.915688","volume":"47","author":"D Micciancio","year":"2001","unstructured":"Micciancio D. The hardness of the closest vector problem with preprocessing. IEEE Trans Inf Theory, 2001, 47: 1212\u20131215","journal-title":"IEEE Trans Inf Theory"},{"key":"4795_CR8","doi-asserted-by":"crossref","first-page":"2031","DOI":"10.1109\/TIT.2004.833350","volume":"50","author":"O Regev","year":"2004","unstructured":"Regev O. Improved inapproximability of lattice and coding problems with preprocessing. IEEE Trans Inf Theory, 2004, 50: 2031\u20132037","journal-title":"IEEE Trans Inf Theory"},{"key":"4795_CR9","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.jcss.2004.01.002","volume":"69","author":"U Feige","year":"2004","unstructured":"Feige U, Micciancio D. The inapproximability of lattice and coding problems with preprocessing. J Comput Syst Sci, 2004, 69: 45\u201367","journal-title":"J Comput Syst Sci"},{"key":"4795_CR10","volume-title":"Technical Report 81\u201304, Math Inst, University of Amsterdam, Amsterdam","author":"P Emde Boas Van","year":"1981","unstructured":"Van Emde Boas P. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81\u201304, Math Inst, University of Amsterdam, Amsterdam, 1981"},{"key":"4795_CR11","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0304-3975(01)00290-0","volume":"285","author":"I Dinur","year":"2002","unstructured":"Dinur I. Approximating SVP\u221e to within almost-polynomial factors is NP-hard. Theor Comput Sci, 2002, 285: 55\u201371","journal-title":"Theor Comput Sci"},{"key":"4795_CR12","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s00493-003-0019-y","volume":"23","author":"I Dinur","year":"2003","unstructured":"Dinur I, Kindler G, Raz R, et al. Approximating CVP to within almost polynomial factors is NP-hard. Combinatorica, 2003, 23: 205\u2013243","journal-title":"Combinatorica"},{"key":"4795_CR13","first-page":"216","volume-title":"Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science","author":"M Alekhnovich","year":"2005","unstructured":"Alekhnovich M, Khot S, Kindler G, et al. Hardness of approximating the closest vector problem with preprocessing. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. Washington DC: IEEE, 2005. 216\u2013225"},{"key":"4795_CR14","first-page":"447","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing","author":"O Regev","year":"2006","unstructured":"Regev O, Rosen R. Lattice problems and norm embeddings. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. New York: ACM, 2006. 447\u2013456"},{"key":"4795_CR15","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1145\/1089023.1089025","volume":"52","author":"D Aharonov","year":"2005","unstructured":"Aharonov D, Regev O. Lattice problems in NP \u2229 coNP. J ACM, 2005, 52: 749\u2013765","journal-title":"J ACM"},{"key":"4795_CR16","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF02574039","volume":"13","author":"W Banaszczyk","year":"1995","unstructured":"Banaszczyk W. Inequalites for convex bodies and polar reciprocal lattices in \u211dn. Discret Comput Geom, 1995, 13: 217\u2013231","journal-title":"Discret Comput Geom"},{"key":"4795_CR17","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1007\/s00037-008-0251-3","volume":"17","author":"C Peikert","year":"2008","unstructured":"Peikert C. Limits on the hardness of lattice problems in l p norms. Comput Complex, 2008, 17: 300\u2013351","journal-title":"Comput Complex"},{"key":"4795_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-90014-2","volume-title":"Lattices and Codes. Advanced Lectures in Mathematics","author":"W Ebeling","year":"2002","unstructured":"Ebeling W. Lattices and Codes. Advanced Lectures in Mathematics. Revised edition. Braunschweig: Friedr Vieweg & Sohn, 2002","edition":"Revised edition"},{"key":"4795_CR19","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1137\/S0097539705447360","volume":"37","author":"D Micciancio","year":"2007","unstructured":"Micciancio D, Regev O. Worst-case to average-case reductions based on Gaussian measures. SIAM J Comput, 2007, 37: 267\u2013302","journal-title":"SIAM J Comput"},{"key":"4795_CR20","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding W. Probability inequalities for sums of bounded random variables. J Am Stat Assoc, 1963, 58: 13\u201330","journal-title":"J Am Stat Assoc"}],"container-title":["Science China Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-013-4795-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11432-013-4795-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-013-4795-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,23]],"date-time":"2020-07-23T22:31:11Z","timestamp":1595543471000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11432-013-4795-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,28]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["4795"],"URL":"https:\/\/doi.org\/10.1007\/s11432-013-4795-8","relation":{},"ISSN":["1674-733X","1869-1919"],"issn-type":[{"value":"1674-733X","type":"print"},{"value":"1869-1919","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,28]]}}}