Abstract
In this paper we introduce a new lattice problem, the subspace avoiding problem (Sap). We describe a probabilistic single exponential time algorithm for Sap for arbitrary ℓ p norms. We also describe polynomial time reductions for four classical problems from the geometry of numbers, the shortest vector problem , the closest vector problem , the successive minima problem , and the shortest independent vectors problem ( ) to Sap, establishing probabilistic single exponential time algorithms for them. The result generalize and extend previous results of Ajtai, Kumar and Sivakumar. The results on and are new for all norms. The results on and generalize previous results of Ajtai et al. for the ℓ2 norm to arbitrary ℓ p norms.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ajtai, M.: The shortest vector problem in l 2 is NP-hard for randomized reductions. In: Proceedings of the 30th ACM Symposium on Theory of Computing, pp. 10–19. ACM Press, New York (1998)
Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the 33th ACM Symposium on Theory of Computing, pp. 601–610. ACM Press, New York (2001)
Ajtai, M., Kumar, R., Sivakumar, D.: Sampling short lattice vectors and the closest lattice vector problem. In: Proceedings of the 17th IEEE Annual Conference on Computational Complexity - CCC, pp. 53–57. IEEE Computer Society Press, Los Alamitos (2002)
Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986)
Blömer, J.: Closest vectors, successive minima, and dual HKZ-bases of lattices. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 248–259. Springer, Heidelberg (2000)
Blömer, J., Seifert, J.-P.: The complexity of computing short linearly independent vectors and sort bases in a lattice. In: Proceedings of the 21th Symposium on Theory of Computing, pp. 711–720 (1999)
Dyer, M., Frieze, A., Kannan, R.: A random polynomial time algorithm for approximating the volume of convex bodies. Journal of the ACM 38(1), 1–17 (1991)
Dinur, I., Kindler, G., Raz, R., Safra, S.: Approximating CVP to within almost-polynomial factors in NP-hard. Combinatorica 23(2), 205–243 (2003)
Kannan, R.: Algorithmic geometry of numbers. Annual Reviews in Computer Science 2, 231–267 (1987)
Kannan, R.: Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research 12(3), 415–440 (1987)
Khot, S.: Hardness of approximating the shortest vector problem in lattices. Journal of the ACM (JACM) 52(5), 789–808 (2005)
Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515–534 (1982)
Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems - A Cryptographic Perspective. Kluwer Academic Publishers, Dordrecht (2002)
Micciancio, D.: The shortest vector in a lattice is hard to approximate to within some constant. SIAM Journal on Computing 30(6), 2008–2035 (2000)
Regev, O.: Lecture note on lattices in computer science, lecture 8: 2O(n)-time algorithm for SVP (2004)
Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science 53, 201–224 (1987)
Schnorr, C.-P.: Block reduced lattice bases and successive minima. Combinatorics, Probability & Computing 3, 507–522 (1994)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blömer, J., Naewe, S. (2007). Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds) Automata, Languages and Programming. ICALP 2007. Lecture Notes in Computer Science, vol 4596. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73420-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-73420-8_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73419-2
Online ISBN: 978-3-540-73420-8
eBook Packages: Computer ScienceComputer Science (R0)