The Hardness of the Closest Vector Problem With Preprocessing Overell_inftyNorm

DOI10.1109/TIT.2006.881835MaRDI QIDQ3548137zbMATH OpenOpenAlexFDO

Authors Wenbin Chen, Jiangtao Meng

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.2006.881835

Mathematics Subject Classification ID

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

Recommendations

• The hardness of the closest vector problem with preprocessing
• The inapproximability of lattice and coding problems with preprocessing
• \(2^{\log^{1-\varepsilon} n}\) hardness for the closest vector problem with preprocessing
• Almost polynomial factor hardness for closest vector problem with preprocessing
• Improved Inapproximability of Lattice and Coding Problems With Preprocessing

Cited in

(15)

• Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix
• The inapproximability of lattice and coding problems with preprocessing
• Inapproximability results for the minimum integral solution problem with preprocessing over \(\ell_{\infty}\) norm
• Lattice problems and norm embeddings
• Almost polynomial factor hardness for closest vector problem with preprocessing
• Improved Inapproximability of Lattice and Coding Problems With Preprocessing
• scientific article; zbMATH DE number 634031 (Why is no real title available?)
• Computing the norm ∥A∥∞,1 is NP-hard^∗
• The hardness of the closest vector problem with preprocessing
• An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm
• Cryptanalysis of NTRU where the private polynomial has one or more consecutive zero coefficients
• \(2^{\log^{1-\varepsilon} n}\) hardness for the closest vector problem with preprocessing
• A Digital Signature Scheme Based on CVP  ∞
• Approximating closest vector problem in \(\ell_\infty\) norm revisited
• A polynomial time algorithm for GapCVPP in \(l_1\) norm

This page was built for publication: The Hardness of the Closest Vector Problem With Preprocessing Over$ell_infty$Norm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548137)