Hardness of approximating the closest vector problem with pre-processing

DOI10.1007/S00037-011-0031-3MaRDI QIDQ430834zbMATH OpenOpenAlexFDO

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

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

latticesapproximationcodeshardnesspreprocessing

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(5)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q430834)