Almost polynomial factor hardness for closest vector problem with preprocessing

DOI10.1137/130919623MaRDI QIDQ3190696zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi

Publication date 18 September 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/130919623

zbMATH Keywords

hardness of approximationclosest vector problemsmooth label coversum check protocol

Mathematics Subject Classification ID

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

Recommendations

• \(2^{\log^{1-\varepsilon} n}\) hardness for the closest vector problem with preprocessing
• The hardness of the closest vector problem with preprocessing
• The inapproximability of lattice and coding problems with preprocessing
• Improved Inapproximability of Lattice and Coding Problems With Preprocessing
• The Hardness of the Closest Vector Problem With Preprocessing Over$ell_infty$Norm

Cited in

(6)

• The hardness of the closest vector problem with preprocessing
• The Hardness of the Closest Vector Problem With Preprocessing Over$ell_infty$Norm
• A polynomial time algorithm for GapCVPP in \(l_1\) norm
• The inapproximability of lattice and coding problems with preprocessing
• \(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: Almost polynomial factor hardness for closest vector problem with preprocessing

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