{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T19:40:11Z","timestamp":1686598811862},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1007\/s00037-011-0031-3","type":"journal-article","created":{"date-parts":[[2012,1,2]],"date-time":"2012-01-02T06:41:17Z","timestamp":1325486477000},"page":"741-753","source":"Crossref","is-referenced-by-count":7,"title":["Hardness of Approximating the Closest Vector Problem with Pre-Processing"],"prefix":"10.1007","volume":"20","author":[{"given":"Mikhail","family":"Alekhnovich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subhash A.","family":"Khot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Kindler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nisheeth K.","family":"Vishnoi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,1,3]]},"reference":[{"key":"31_CR1","unstructured":"Dorit Aharonov & Oded Regev (2005). Lattice problems in NP $${\\cap}$$ co-NP. J. ACM 52, 749\u2013765. ISSN 0004-5411. URL http:\/\/doi.acm.org\/10.1145\/1089023.1089025 ."},{"key":"31_CR2","unstructured":"M. Ajtai (1996). Generating hard instances of lattice problems. In Proceedings of the ACM Symposium on the Theory of Computing, number 28, 99\u2013108."},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"Mikhail Alekhnovich, Subhash Khot, Guy Kindler & Nisheeth K. Vishnoi (2005). Hardness of Approximating the Closest Vector Problem with Pre-Processing. In Proceedings of the 46nd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh PA, 216\u2013225.","DOI":"10.1109\/SFCS.2005.40"},{"issue":"2","key":"31_CR4","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1109\/18.52484","volume":"36","author":"J. Bruck","year":"1990","unstructured":"Bruck J., Naor M. (1990) The hardness of decoding linear codes with preprocessing. IEEE Transactions on Information Theory 36(2): 381\u2013385","journal-title":"IEEE Transactions on Information Theory"},{"issue":"5","key":"31_CR5","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1137\/S0097539704443057","volume":"34","author":"Dinur Irit","year":"2005","unstructured":"Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev (2005) A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. SIAM J. Comput. 34(5): 1129\u20131146","journal-title":"SIAM J. Comput."},{"issue":"2","key":"31_CR6","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s00493-003-0019-y","volume":"23","author":"Dinur Irit","year":"2003","unstructured":"Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra (2003) Approximating CVP to Within Almost-Polynomial Factors is NP-Hard. Combinatorica 23(2): 205\u2013243","journal-title":"Combinatorica"},{"issue":"1","key":"31_CR7","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. (2004) The inapproximability of lattice and coding problems with preprocessing. Journal of Computer and System Sciences 69(1): 45\u201367","journal-title":"Journal of Computer and System Sciences"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"R. Kannan (1983). Improved algorithms for integer programming and related lattice problems. In Proceedings of the ACM Symposium on the Theory of Computing, number 15, 193\u2013206.","DOI":"10.1145\/800061.808749"},{"key":"31_CR9","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF02128669","volume":"10","author":"J.C. Lagarias","year":"1990","unstructured":"Lagarias J.C., Lenstra H.W., Schnorr C.P. (1990) Korkine-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica 10: 333\u2013348","journal-title":"Combinatorica"},{"issue":"1","key":"31_CR10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"J.C. Lagarias","year":"1985","unstructured":"Lagarias J.C., Odlyzko A.M. (1985) Solving low-density subset sum problems. Journal of the ACM 32(1): 229\u2013246","journal-title":"Journal of the ACM"},{"key":"31_CR11","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. (1982) Factoring polynomials with rational coefficients. Math. Ann. 261: 513\u2013534","journal-title":"Math. Ann."},{"key":"31_CR12","unstructured":"H.W. Lenstra (1981). Integer programming with a fixed number of variables. Technical Report 81-03, Univ. of Amsterdam, Amsterdam."},{"key":"31_CR13","unstructured":"Yi-Kai Liu, Vadim Lyubashevsky & Daniele Micciancio (2006). On Bounded Distance Decoding for General Lattices. In APPROX-RANDOM, 450\u2013461."},{"issue":"5","key":"31_CR14","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"Lund. Carsten","year":"1994","unstructured":"Carsten Lund., Mihalis Yannakakis (1994) On the Hardness of Approximating Minimization Problems. J. ACM 41(5): 960\u2013981","journal-title":"J. ACM"},{"key":"31_CR15","doi-asserted-by":"crossref","first-page":"1212","DOI":"10.1109\/18.915688","volume":"47","author":"D. Micciancio","year":"2001","unstructured":"Micciancio D. (2001) The Hardness of the Closest Vector Problem with Preprocessing. IEEE Transactions on Information Theory 47: 1212\u20131215","journal-title":"IEEE Transactions on Information Theory"},{"key":"31_CR16","unstructured":"D. Micciancio & S. Goldwasser (2002). Complexity of lattice problems: A cryptographic perspective, volume 671. Kluwer Academic Publishers."},{"key":"31_CR17","unstructured":"Daniele Micciancio & Panagiotis Voulgaris (2010). A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In Proceedings of the ACM Symposium on the Theory of Computing, 351\u2013358."},{"key":"31_CR18","unstructured":"Phong Quang Nguyen (2010). Hermite\u2019s Constant and Lattice Algorithms. In The LLL Algorithm: Survey and Applications, Phong Q. Nguyen & Brigitte Vall\u00e9e, editors, Information Security and Cryptography Series, 19\u201369. Springer."},{"issue":"9","key":"31_CR19","doi-asserted-by":"crossref","first-page":"2031","DOI":"10.1109\/TIT.2004.833350","volume":"50","author":"Regev Oded","year":"2004","unstructured":"Oded Regev (2004) Improved Inapproximability of Lattice and Coding Problems With Preprocessing. IEEE Transactions on Information Theory 50(9): 2031\u20132037","journal-title":"IEEE Transactions on Information Theory"},{"key":"31_CR20","doi-asserted-by":"crossref","unstructured":"Oded Regev & Ricky Rosen (2006). Lattice problems and norm embeddings. In Proceedings of the ACM Symposium on the Theory of Computing, 447\u2013456.","DOI":"10.1145\/1132516.1132581"},{"key":"31_CR21","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"Schnorr Claus-Peter","year":"1987","unstructured":"Claus-Peter Schnorr (1987) A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms. Theor. Comput. Sci. 53: 201\u2013224","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"31_CR22","doi-asserted-by":"crossref","first-page":"1710","DOI":"10.1109\/18.556667","volume":"42","author":"Sipser. Michael","year":"1996","unstructured":"Michael Sipser., Daniel A. Spielman (1996) Expander codes. IEEE Transactions on Information Theory 42(6): 1710\u20131722","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0031-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0031-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0031-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T19:12:46Z","timestamp":1686597166000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0031-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["31"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0031-3","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}