Hardness of approximating the closest vector problem with pre-processing
DOI10.1007/S00037-011-0031-3zbMATH Open1252.68132OpenAlexW2034056530MaRDI QIDQ430834FDOQ430834
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
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
- A hierarchy of polynomial time lattice basis reduction algorithms
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- Factoring polynomials with rational coefficients
- Expander codes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lattice problems and norm embeddings
- On the hardness of approximating minimization problems
- Solving low-density subset sum problems
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Approximating CVP to within almost-polynomial factors is NP-hard
- The hardness of decoding linear codes with preprocessing
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
- The inapproximability of lattice and coding problems with preprocessing
- Improved Inapproximability of Lattice and Coding Problems With Preprocessing
- On Bounded Distance Decoding for General Lattices
- Lattices and factorization of polynomials
- Hardness of approximating the closest vector problem with pre-processing
- The hardness of the closest vector problem with preprocessing
Cited In (5)
- 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
- 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
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)
