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. Krajicek, 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.. \newblock {\em Journal f"ur 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. [ .pdf ]
[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].

This file has been generated by bibtex2html 1.85.