Approximating CVP to within almost-polynomial factors is NP-hard

DOI10.1007/S00493-003-0019-YzbMath1049.68072OpenAlexW3014312596WikidataQ57567992 ScholiaQ57567992MaRDI QIDQ1878613

Ran Raz, Guy Kindler, Irit Dinur, 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

zbMATH Keywords

approximation NP-hardness closest vector problem lattice problems constraint satisfiability problem for finite domains Super Sat

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (35)

Approximating multidimensional subset sum and Minkowski decomposition of polygons ⋮ The inapproximability of lattice and coding problems with preprocessing ⋮ Covering convex bodies and the closest vector problem ⋮ Voronoi Cells of Lattices with Respect to Arbitrary Norms ⋮ An improved lower bound for approximating shortest integer relation in $\ell _{\infty }$ norm $(SIR_{\infty })$ ⋮ Matrix sparsification and the sparse null space problem ⋮ Approximate CVP in time $2^{0.802 n}$ -- now in any norm! ⋮ Ciphertext-only attacks against compact-LWE submitted to NIST PQC project ⋮ NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem ⋮ A polynomial time algorithm for GapCVPP in $l_1$ norm ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Hardness of approximating the closest vector problem with pre-processing ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ An improved lower bound for approximating minimum GCD multiplier in $\ell _\infty $ norm (GCDM$_\infty$) ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ An improved lower bound for approximating the minimum integral solution problem with preprocessing over $\ell_\infty$ norm ⋮ Voronoi polytopes for polyhedral norms on lattices ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ A semidefinite programming method for integer convex quadratic minimization ⋮ A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices ⋮ Restricted parameter range promise set cover problems are easy ⋮ Hardness of approximating the shortest vector problem in high $\ell_{p}$ norms ⋮ Complexity and algorithms for computing Voronoi cells of lattices ⋮ A Digital Signature Scheme Based on CVP ∞ ⋮ Improvements in the analysis of Kannan's CVP algorithm ⋮ Sampling methods for shortest vectors, closest vectors and successive minima ⋮ Approximate CVP$_p$ in time $2^{0.802n}$ ⋮ Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle ⋮ The Geometry of Lattice Cryptography ⋮ Hardness of approximating the minimum solutions of linear Diophantine equations ⋮ A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. ⋮ A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor ⋮ The remote set problem on lattices ⋮ Approximating $SVP_{\infty}$ to within almost-polynomial factors is NP-hard

This page was built for publication: Approximating CVP to within almost-polynomial factors is NP-hard