pith. sign in

arxiv: 1109.2176 · v1 · pith:ME5XD4NTnew · submitted 2011-09-10 · 💻 cs.CC · cs.DS

2^{log^(1-eps) n} Hardness for Closest Vector Problem with Preprocessing

classification 💻 cs.CC cs.DS
keywords problemclosestdeltafactorhardnesspreprocessingvectorakkv05
0
0 comments X
read the original abstract

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not \subseteq$DTIME$(2^{{\log^{O(1/\eps)} n}})$, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than $2^{\log ^{1-\eps}n}.$ This improves upon the previous hardness factor of $(\log n)^\delta$ for some $\delta > 0$ due to \cite{AKKV05}.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.