The inapproximability of lattice and coding problems with preprocessing

DOI10.1016/j.jcss.2004.01.002zbMath1106.68046OpenAlexW2083175934MaRDI QIDQ1881262

Daniele Micciancio, Uriel Feige

Publication date: 4 October 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.01.002

zbMATH Keywords

NP-hardnesscoding theoryapproximation problemsclosest vector problempoint latticesnearest codeword problempreprocessing computational complexity

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem ⋮ A polynomial time algorithm for GapCVPP in \(l_1\) norm ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ Hardness of approximating the closest vector problem with pre-processing ⋮ An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm ⋮ The Restricted Isometry Property of Subsampled Fourier Matrices

Uses Software

• CVPP

Cites Work

• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• Solvability by radicals is in polynomial time
• Factoring polynomials with rational coefficients
• Improved low-density subset sum algorithms
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Approximating CVP to within almost-polynomial factors is NP-hard
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
• Integer Programming with a Fixed Number of Variables
• Disproof of the Mertens conjecture.
• The hardness of decoding linear codes with preprocessing
• The intractability of computing the minimum distance of a code
• The hardness of the closest vector problem with preprocessing
• Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor
• Hardness of approximating the minimum distance of a linear code
• Advances in Cryptology - CRYPTO 2003
• Some optimal inapproximability results
• The hardness of solving subset sum with preprocessing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The inapproximability of lattice and coding problems with preprocessing