Hardness of approximating the closest vector problem with pre-processing

DOI10.1007/S00037-011-0031-3zbMath1252.68132OpenAlexW2034056530MaRDI QIDQ430834

Nisheeth K. Vishnoi, Guy Kindler, Subhash A. Khot, Michael Alekhnovich

Publication date: 26 June 2012

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-011-0031-3

zbMATH Keywords

approximationlatticeshardnesscodespreprocessing

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Sieving for closest lattice vectors (with preprocessing) ⋮ Hardness of approximating the closest vector problem with pre-processing ⋮ Special issue in memory of Misha Alekhnovich. Foreword ⋮ An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm

Cites Work

• Unnamed Item
• Unnamed Item
• Hardness of approximating the closest vector problem with pre-processing
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Approximating CVP to within almost-polynomial factors is NP-hard
• The inapproximability of lattice and coding problems with preprocessing
• A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
• Lattice problems and norm embeddings
• Expander codes
• The hardness of decoding linear codes with preprocessing
• Improved Inapproximability of Lattice and Coding Problems With Preprocessing
• On Bounded Distance Decoding for General Lattices
• Solving low-density subset sum problems
• Lattices and factorization of polynomials
• On the hardness of approximating minimization problems
• The hardness of the closest vector problem with preprocessing
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

This page was built for publication: Hardness of approximating the closest vector problem with pre-processing