Approximating CVP to within almost-polynomial factors is NP-hard
DOI10.1007/S00493-003-0019-YzbMATH Open1049.68072OpenAlexW3014312596WikidataQ57567992 ScholiaQ57567992MaRDI QIDQ1878613FDOQ1878613
Authors: Ran Raz, Irit Dinur, Guy Kindler, Shmuel Safra 
Publication date: 7 September 2004
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-003-0019-y
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
approximationNP-hardnessclosest vector problemlattice problemsconstraint satisfiability problem for finite domainsSuper Sat
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (41)
- 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
- The geometry of lattice cryptography
- The remote set problem on lattices
- An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\)
- 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
- Approximate CVP_p in Time 2^{0.802 n}
- A distance metric-based space-filling subsampling method for nonparametric models
- A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor
- 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
- Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
- The inapproximability of lattice and coding problems with preprocessing
- Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
- Hardness of approximating the minimum solutions of linear Diophantine equations
- Approximate CVP\(_p\) in time \(2^{0.802n}\)
- A polynomial time algorithm for solving the closest vector problem in zonotopal lattices
- Verification of NP-Hardness Reduction Functions for Exact Lattice Problems
- Complexity and algorithms for computing Voronoi cells of lattices
- 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 the closest vector problem using an approximate shortest vector oracle
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- Improvements in the analysis of Kannan's CVP algorithm
- 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)
