Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle

Details Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle

2011-06-14

arxiv.org/abs/1106.2619v2

Computer Science

Data Structures and Algorithms

10 pages, Published in APPROX 2011

Scientific paper

We give a polynomial time Turing reduction from the
$\gamma^2\sqrt{n}$-approximate closest vector problem on a lattice of dimension
$n$ to a $\gamma$-approximate oracle for the shortest vector problem. This is
an improvement over a reduction by Kannan, which achieved $\gamma^2n^{3/2}$.

Affiliated with

Also associated with

No associations

Rating

Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle 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 Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-113188