Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem

by Miklós Ajtai

Theory of Computing, Volume 4(2), pp. 21-51, 2008

Bibliography with links to cited articles

[1]   M. Ajtai: Random lattices and a conjectured 0—1 law about their polynomial time computable properties. In Proc. 43rd FOCS, pp. 733–742. IEEE Computer Society, 2002. [FOCS:10.1109/SFCS.2002.1181998].

[2]    M. Ajtai: The worst-case behavior of Schnorr’s algorithm approximating the shortest nonzero vector in a lattice. In Proc. 35th STOC, pp. 396–406. ACM Press, 2003. [STOC:10.1145/780542.780602].

[3]   M. Ajtai: Generating hard instances of lattice problems. In J. Krajiček, editor, Complexity of computations and proofs, volume 13 of Quaderni di Matematica, pp. 1–32. Seconda Universita di Napoli, 2004. Preliminary version: Proc. 28th STOC, 1996, pp. 99–108.

[4]   M. Ajtai, R. Kumar, and D. Sivakumar: A sieve algorithm for the shortest lattice vector problem. In Proc. 33rd STOC, pp. 601–610. ACM Press, 1996. [STOC:10.1145/380752.380857].

[5]   M. L. Furst and R. Kannan: Succinct certificates for almost all subset problems. SIAM Journal on Computing, 18:550–558, 1989. [SICOMP:10.1137/0218037].

[6]   C. F. Gauss: Recursion der “untersuchungen über die eigenschaften der positiven ternären quadratische formen von ludwig august seeber, dr. der philosophie, ordentl. professor der universität in freiburg, 1831, 248 s. in 4.”. Journal für die reine und angewandte Mathematik, 20:312–320, 1840.

[7]   A. M. Odlyzko J. C. Lagarias: Solving low-density subset sum problems. Journal of the Association for Computing Machinery, 32(1):229–246, 1985. [JACM:10.1145/2455.2461].

[8]   R. Kannan: Algorithmic geometry of numbers. In Annual Review of Computer Science, volume 2, pp. 231–269. Annual Reviews Inc., 1987.

[9]   R. Kannan: Minkowski’s convex body theorem and integer programming. Mathematics of Operation Research, 12(3):415–440, 1987.

[10]   A. Korkine and G. Zolotareff: Sur les formes quadratiques. Mathematische Annalen, 6:366–389, 1873. [Springer:p56345710m4p6214].

[11]   J. L. Lagrange: Recherches d’arithmétique. In M. J.-A. Serret, editor, Oeuvres de Lagrange, volume 3, pp. 698–701. Gauthier-Villars, 1869. (article cca 1773).

[12]   A. K. Lenstra, H. W. Lenstra, and L. Lovász: Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515–534, 1982. [Springer:lh1m24436431g068].

[13]   A. M. Odlyzko and H. te Riele: Disproof of the Mertens conjecture. Journal für die reine und angewandte Mathematik, 357:138–160, 1985.

[14]   C.-P. Schnorr: A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 53:201–224, 1987. [TCS:10.1016/0304-3975(87)90064-8].

[15]   C.-P. Schnorr: Lattice reduction by random sampling and birthday methods. In Proc. 20th Ann. Symp. on Theoretical Aspects of Computer Science (STACS’03), volume 2607 of Lecture Notes in Computer Science, pp. 145–156. Springer, 2003. [STACS:qjpadpmwabty52g4].