Improved Inapproximability of Lattice and Coding Problems With Preprocessing
From MaRDI portal
Publication:3547549
DOI10.1109/TIT.2004.833350zbMath1315.94036OpenAlexW2060296335MaRDI QIDQ3547549
Publication date: 21 December 2008
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/tit.2004.833350
computational complexitylinear codesNP-hardnessCVPNCPnearest codeword problemClosest vector problemrelatively nearest codeword problemRNCP
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Source coding (94A29)
Related Items
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 ⋮ Min sum clustering with penalties
This page was built for publication: Improved Inapproximability of Lattice and Coding Problems With Preprocessing