Approximating CVP to within almost-polynomial factors is NP-hard
From MaRDI portal
(Redirected from Publication:1878613)
Recommendations
- On the limits of nonapproximability of lattice problems
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
- Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix
- scientific article; zbMATH DE number 1507221
Cited in
(41)- Improvements in the analysis of Kannan's CVP algorithm
- A Digital Signature Scheme Based on CVP ∞
- Ciphertext-only attacks against compact-LWE submitted to NIST PQC project
- Voronoi polytopes for polyhedral norms on lattices
- An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\)
- The geometry of lattice cryptography
- The remote set problem on lattices
- Economical convex coverings and applications
- A semidefinite programming method for integer convex quadratic minimization
- The projection games conjecture and the hardness of approximation of Super-SAT and related problems
- Hardness of approximating the closest vector problem with pre-processing
- A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor
- Approximate CVP_p in Time 2^{0.802 n}
- A distance metric-based space-filling subsampling method for nonparametric models
- Approximating multidimensional subset sum and Minkowski decomposition of polygons
- Voronoi cells of lattices with respect to arbitrary norms
- Restricted parameter range promise set cover problems are easy
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
- Covering convex bodies and the closest vector problem
- A polynomial time algorithm for GapCVPP in \(l_1\) norm
- Approximating closest vector problem in \(\ell_\infty\) norm revisited
- The inapproximability of lattice and coding problems with preprocessing
- Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
- Hardness of approximating the minimum solutions of linear Diophantine equations
- Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
- Approximate CVP\(_p\) in time \(2^{0.802n}\)
- A polynomial time algorithm for solving the closest vector problem in zonotopal lattices
- Complexity and algorithms for computing Voronoi cells of lattices
- Verification of NP-Hardness Reduction Functions for Exact Lattice Problems
- Parameterized intractability of even set and shortest vector problem from Gap-ETH
- NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem
- Lattice problems beyond polynomial time
- Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix
- Sampling methods for shortest vectors, closest vectors and successive minima
- An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm
- On the smallest ratio problem of lattice bases
- An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- Approximating the closest vector problem using an approximate shortest vector oracle
- A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
- On the complexity of quasiconvex integer minimization problem
This page was built for publication: Approximating CVP to within almost-polynomial factors is NP-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1878613)
