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

Details $2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing $2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing

2011-09-10

arxiv.org/abs/1109.2176v1

Computer Science

Computational Complexity

Scientific paper

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}.

Affiliated with

Also associated with

No associations

Rating

$2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with $2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and $2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-38330