The Hardness of the Closest Vector Problem With Preprocessing Overell_inftyNorm

DOI10.1109/TIT.2006.881835zbMATH Open1323.68296OpenAlexW1981627190MaRDI QIDQ3548137FDOQ3548137

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

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

Mathematics Subject Classification ID

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

Cited In (15)

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

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)