Sampling methods for shortest vectors, closest vectors and successive minima

DOI10.1016/j.tcs.2008.12.045zbMath1220.68057OpenAlexW2070971235MaRDI QIDQ1014636

Stefanie Naewe, Johannes Blömer

Publication date: 29 April 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.045

zbMATH Keywords

latticesgeometry of numbersshortest vectors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06) Approximation algorithms (68W25)

Related Items

Covering convex bodies and the closest vector problem ⋮ Voronoi Cells of Lattices with Respect to Arbitrary Norms ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ From approximate to exact integer programming ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Quantum blockchain-enabled exchange protocol model for decentralized systems ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ On lattice-based algebraic feedback shift registers synthesis for multisequences ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ The Reductions for the Approximating Covering Radius Problem ⋮ A randomized sieving algorithm for approximate integer programming ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ FPT-algorithms for some problems related to integer programming ⋮ Unnamed Item ⋮ Improvements in the analysis of Kannan's CVP algorithm ⋮ Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices ⋮ Approximate CVP\(_p\) in time \(2^{0.802n}\) ⋮ Unnamed Item

Cites Work

• On Lovász' lattice reduction and the nearest lattice point problem
• Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• On the limits of nonapproximability of lattice problems
• Approximating CVP to within almost-polynomial factors is NP-hard
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
• On the complexity of computing short linearly independent vectors and short bases in a lattice
• Lattice problems and norm embeddings
• Hardness of approximating the shortest vector problem in lattices
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• Minkowski's Convex Body Theorem and Integer Programming
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Block Reduced Lattice Bases and Successive Minima
• A sieve algorithm for the shortest lattice vector problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item