2^^1- n hardness for the closest vector problem with preprocessing

DOI10.1145/2213977.2214004MaRDI QIDQ5415481zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi

Publication date 13 May 2014

Published in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2213977.2214004

zbMATH Keywords

closest vector problemhardness of approximationlatticesnearest codeword problemPCP

Mathematics Subject Classification ID

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

Recommendations

• Almost polynomial factor hardness for 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 Overell_inftyNorm

Cited in

(6)

• The inapproximability of lattice and coding problems with preprocessing
• On succinct arguments and witness encryption from groups
• Almost polynomial factor hardness for closest vector problem with preprocessing
• Improved Inapproximability of Lattice and Coding Problems With Preprocessing
• The Hardness of the Closest Vector Problem With Preprocessing Overell_inftyNorm
• The hardness of the closest vector problem with preprocessing

This page was built for publication: \(2^{\log^{1-\varepsilon} n}\) hardness for the closest vector problem with preprocessing

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