Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
From MaRDI portal
Publication:2164729
DOI10.1007/978-3-031-06901-7_33zbMath1497.90134arXiv2110.02387OpenAlexW3203598337MaRDI QIDQ2164729
Publication date: 16 August 2022
Full work available at URL: https://arxiv.org/abs/2110.02387
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Limits on the hardness of lattice problems in \(\ell_{p}\) norms
- Sampling methods for shortest vectors, closest vectors and successive minima
- On Lovász' lattice reduction and the nearest lattice point problem
- A hierarchy of polynomial time lattice basis reduction algorithms
- Factoring polynomials with rational coefficients
- On the limits of nonapproximability of lattice problems
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
- Approximating CVP to within almost-polynomial factors is NP-hard
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Approximate CVP\(_p\) in time \(2^{0.802n}\)
- Covering convex bodies and the closest vector problem
- 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
- A O(1/ε 2) n -Time Sieving Algorithm for Approximate Integer Programming
- Lattice problems and norm embeddings
- Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling
- Integer Programming with a Fixed Number of Variables
- Lattice problems in NP ∩ coNP
- Hardness of approximating the shortest vector problem in lattices
- Minkowski's Convex Body Theorem and Integer Programming
- Discrete Gaussian Sampling Reduces to CVP and SVP
- Fully homomorphic encryption using ideal lattices
- 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)
- Covering cubes and the closest vector problem
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- On lattices, learning with errors, random linear codes, and cryptography
This page was built for publication: Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
