Hardness of approximating the closest vector problem with pre-processing

DOI10.1007/s00037-011-0031-3zbMath1252.68132MaRDI QIDQ430834

Michael Alekhnovich, Subhash A. 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

approximation; lattices; hardness; codes; preprocessing

Mathematics Subject Classification ID

11Y16: Number-theoretic algorithms; complexity

11H06: Lattices and convex bodies (number-theoretic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Hardness of approximating the closest vector problem with pre-processing, Special issue in memory of Misha Alekhnovich. Foreword

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