A New Reduction from Search SVP to Optimization SVP

Details A New Reduction from Search SVP to Optimization SVP A New Reduction from Search SVP to Optimization SVP

2012-04-10

arxiv.org/abs/1204.2040v1

Computer Science

Computational Complexity

Scientific paper

It is well known that search SVP is equivalent to optimization SVP. However, the former reduction from search SVP to optimization SVP by Kannan needs polynomial times calls to the oracle that solves the optimization SVP. In this paper, a new rank-preserving reduction is presented with only one call to the optimization SVP oracle. It is obvious that the new reduction needs the least calls, and improves Kannan's classical result. What's more, the idea also leads a similar direct reduction from search CVP to optimization CVP with only one call to the oracle.

Affiliated with

Also associated with

No associations

Rating

A New Reduction from Search SVP to Optimization SVP 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 A New Reduction from Search SVP to Optimization SVP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A New Reduction from Search SVP to Optimization SVP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-644343