Sampling methods for shortest vectors, closest vectors and successive minima
From MaRDI portal
Publication:1014636
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
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
