Improved Inapproximability of Lattice and Coding Problems With Preprocessing
From MaRDI portal
Publication:3547549
DOI10.1109/TIT.2004.833350zbMath1315.94036MaRDI QIDQ3547549
Publication date: 21 December 2008
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
computational complexity; linear codes; NP-hardness; CVP; NCP; nearest codeword problem; Closest vector problem; relatively nearest codeword problem; RNCP
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
94A29: Source coding
Related Items
NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem, Hardness of approximating the closest vector problem with pre-processing, A polynomial time algorithm for GapCVPP in \(l_1\) norm, Min sum clustering with penalties, Sieving for closest lattice vectors (with preprocessing)