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

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