{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:07:04Z","timestamp":1787386024807,"version":"3.56.0"},"reference-count":35,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3827,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,3]]},"DOI":"10.1016\/s0166-218x(02)00216-0","type":"journal-article","created":{"date-parts":[[2002,10,28]],"date-time":"2002-10-28T16:05:14Z","timestamp":1035821114000},"page":"9-31","source":"Crossref","is-referenced-by-count":12,"title":["A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor"],"prefix":"10.1016","volume":"126","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(02)00216-0_BIB1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, Generating hard instances of lattice problems, in: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, 1996. Full version available from ECCC, Electronic Colloquium on Computational Complexity TR96-007, http:\/\/www.eccc.uni-trier.de\/eccc\/.","DOI":"10.1145\/237814.237838"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB2","unstructured":"M. Ajtai, The shortest vector problem in L2 is NP-hard for randomized reductions, Electronic Colloquium on Computational Complexity TR97-047, http:\/\/www.eccc.uni-trier.de\/eccc\/."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB3","doi-asserted-by":"crossref","unstructured":"M. Ajtai, C. Dwork, A public-key cryptosystem with worst-case\/average-case equivalence, 1996, Available from ECCC, Electronic Colloquium on Computational Complexity TR96-065, http:\/\/www.eccc.uni-trier.de\/eccc\/.","DOI":"10.1145\/258533.258604"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB4","doi-asserted-by":"crossref","unstructured":"S. Arora, L. Babai, J. Stern, Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, in: Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS), 1993, pp. 724\u2013733.","DOI":"10.1109\/SFCS.1993.366815"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579403","article-title":"On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem","volume":"6","author":"Babai","year":"1986","journal-title":"Combinatorica"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB6","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","year":"1993","journal-title":"Math. Ann."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB7","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/BF02711514","article-title":"Inequalities for convex bodies and polar reciprocal lattices in Rn II","volume":"16","author":"Banaszczyk","year":"1996","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB8","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0304-3975(98)00058-9","article-title":"A relation of primal-dual lattices and the complexity of shortest lattice vector problem","volume":"207","author":"Cai","year":"1998","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB9","unstructured":"J.-Y. Cai, A. Nerurkar, An improved worst-case to average-case connection for lattice problems, in: Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS), 1997, pp. 468\u2013477."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB10","doi-asserted-by":"crossref","unstructured":"J.-Y. Cai, A. Nerurkar, Approximating the SVP to within a factor (1+1dimxi) is NP-hard under randomized reductions; J. Comput. Syst. Sci. (1999) 221\u2013239.","DOI":"10.1006\/jcss.1999.1649"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB11","series-title":"An Introduction to the Geometry of Numbers","author":"Cassels","year":"1959"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB12","doi-asserted-by":"crossref","unstructured":"I. Dinur, Approximating SVP\u221e to within almost-polynomial factors is NP-hard, Available from ECCC as TR99-016.","DOI":"10.1109\/SFCS.1998.743433"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB13","doi-asserted-by":"crossref","unstructured":"I. Dinur, G. Kindler, R. Raz, S. Safra, Approximating CVP to within almost-polynomial factors is NP-hard, manuscript, 1999.","DOI":"10.1007\/3-540-46521-9_22"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB14","unstructured":"I. Dinur, G. Kindler, S. Safra, Approximating CVP to within almost-polynomial factors is NP-hard, Available from ECCC, Electronic Colloquium on Computational Complexity TR98-048, http:\/\/www.eccc.uni-trier.de\/eccc\/."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB15","unstructured":"P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in lattices, Technical Report 81-04, Mathematics Department, University of Amsterdam, 1981."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB16","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","article-title":"The complexity of promise problems with applications to public-key cryptography","volume":"61","author":"Even","year":"1984","journal-title":"Inform. Control"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB17","unstructured":"O. Goldreich, S. Goldwasser, On the limits of non-approximability of lattice problems, Electronic Colloquium on Computational Complexity TR97-031, http:\/\/www.eccc.uni-trier.de\/eccc\/."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB18","unstructured":"O. Goldreich, S. Goldwasser, S. Halevi, Collision-free hashing from lattice problems, 1996, Available from ECCC, Electronic Colloquium on Computational Complexity TR96-042, http:\/\/www.eccc.uni-trier.de\/eccc\/."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB19","unstructured":"O. Goldreich, S. Goldwasser, S. Halevi, Public-key cryptosystems from lattice reduction problems, 1996, Available from ECCC, Electronic Colloquium on Computational Complexity TR96-056, http:\/\/www.eccc.uni-trier.de\/eccc\/."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB20","series-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel","year":"1988"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB21","series-title":"Handbook of Convex Geometry","author":"Gruber","year":"1993"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB22","series-title":"Geometry of Numbers","author":"Gruber","year":"1987"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB23","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":"H\u00e5stad","year":"1988","journal-title":"Combinatorica"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB24","doi-asserted-by":"crossref","unstructured":"E. Hewitt, K.A. Ross, Abstract Harmonic Analysis, Vol II. Springer, Berlin, G\u00f6ttingen Heidelberg, 1970.","DOI":"10.1007\/978-3-662-26755-4"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB25","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1007\/BF01442912","article-title":"Sur les formes quadratiques positives quaternaires","volume":"5","author":"Korkin","year":"1872","journal-title":"Math. Ann."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB26","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0214016","article-title":"The computational complexity of simultaneous diophantine approximation problems","volume":"14","author":"Lagarias","year":"1985","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10.1016\/S0166-218X(02)00216-0_BIB27","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF02128669","article-title":"Korkin\u2013Zolotarev bases and successive minima of a lattice and its reciprocal lattice","volume":"10","author":"Lagarias","year":"1990","journal-title":"Combinatorica"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB28","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","article-title":"Integer programming with a fixed number of variables","volume":"8","author":"Lenstra","year":"1983","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB29","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB30","series-title":"An Algorithmic Theory of Numbers, Graphs and Convexity","author":"Lov\u00e1sz","year":"1986"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB31","doi-asserted-by":"crossref","first-page":"93","DOI":"10.21136\/CPMF.1939.109441","article-title":"Ein \u00dcbertragungsprinzip f\u00fcr konvexe K\u00f6rper","volume":"68","author":"Mahler","year":"1939","journal-title":"\u010cas. P\u011bstov\u00e4n\u0131\u0301 Mat. Fys."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB32","unstructured":"D. Micciancio, The shortest vector in a lattice is hard to approximate to within some constant, Available from ECCC, Electronic Colloquium on Computational Complexity TR98-016, http:\/\/www.eccc.uni-trier.de\/eccc\/."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB33","series-title":"Symmetric Bilinear Forms","author":"Milnor","year":"1973"},{"key":"10.1016\/S0166-218X(02)00216-0_BIB34","first-page":"138","article-title":"Disproof of the Mertens conjecture","volume":"357","author":"Odlyzko","year":"1985","journal-title":"J. f\u00fcr die Reine und Angew. Math."},{"key":"10.1016\/S0166-218X(02)00216-0_BIB35","unstructured":"C.P. Schnorr, A hierarchy of polynomial time basis reduction algorithms, Theory Algor. (1985) 375\u2013386."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02002160?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02002160?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T19:01:09Z","timestamp":1733511669000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X02002160"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,3]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,3]]}},"alternative-id":["S0166218X02002160"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00216-0","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2003,3]]}}}