Approximate CVP_p in Time 2^{0.802 n}
From MaRDI portal
Publication:5874513
DOI10.4230/LIPIcs.ESA.2020.43OpenAlexW3082158639MaRDI QIDQ5874513
Moritz Venzin, Friedrich Eisenbrand
Publication date: 7 February 2023
Full work available at URL: https://doi.org/10.4230/LIPIcs.ESA.2020.43
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On weighted covering numbers and the Levi-Hadwiger conjecture
- Sampling methods for shortest vectors, closest vectors and successive minima
- A hierarchy of polynomial time lattice basis reduction algorithms
- Factoring polynomials with rational coefficients
- Intrinsic volumes and lattice points of crosspolytopes
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
- 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 some covering problems in geometry
- A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
- Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling
- A Geometric Analysis of the AWGN Channel With a <inline-formula> <tex-math notation="LaTeX">$(\sigma , \rho )$ </tex-math> </inline-formula>-Power Constraint
- Integer Programming with a Fixed Number of Variables
- Hardness of approximating the shortest vector problem in lattices
- Minkowski's Convex Body Theorem and Integer Programming
- A Greedy Heuristic for the Set-Covering Problem
- A random polynomial-time algorithm for approximating the volume of convex bodies
- A sieve algorithm for the shortest lattice vector problem
- (Gap/S)ETH hardness of SVP
- Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)
- Convex and Discrete Geometry
- Covering cubes and the closest vector problem
- Convex Bodies The Brunn-MinkowskiTheory
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
This page was built for publication: Approximate CVP_p in Time 2^{0.802 n}