2 log1-ε n hardness for the closest vector problem with preprocessing

DOI10.1145/2213977.2214004zbMath1286.68199OpenAlexW2142236338MaRDI QIDQ5415481

Preyas Popat, Subhash A. Khot, 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

latticeshardness of approximationclosest vector problemPCPnearest codeword problem

Mathematics Subject Classification ID

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

Related Items (1)

On succinct arguments and witness encryption from groups

This page was built for publication: 2 ^{log1-ε n} hardness for the closest vector problem with preprocessing