<p>The short answer is &quot;yes,&quot; but with several caveats, maybe the most important of which is that all known such reductions from CVP to SVP in the Euclidean norm are randomized. Self promotion: check out Section 3 of <a href="https://eccc.weizmann.ac.il/report/2022/170/" rel="noreferrer">my survey on SVP</a>.</p>

CC BY-SA 4.0
2023-07-01T06:31:36.743Z
I see only a reduction from GapCVP using Kannan's embedding but not from CVP to SVP.
Turbo
CC BY-SA 4.0
2023-07-01T07:14:47.467Z
The reductions described there are between the decision (Gap) versions of the problems (and in fact from a variant of GapCVP), but also works for the search versions. (Kannan's embedding isn't a valid reduction by itself.)
Huck Bennett
CC BY-SA 4.0
2023-07-01T07:18:20.167Z
Perhaps I am new to the area and so I don't know. Isn't CVP different from GapCVP?
Turbo
CC BY-SA 4.0
2023-07-01T16:49:19.673Z
"Gap" just means the decision version. This is explained in the introduction!
Huck Bennett
CC BY-SA 4.0
2023-07-01T00:21:04.113Z
2023-07-01T00:21:04.113Z
Huck Bennett
<p>The notes here provide a reduction from <span class="math-container">$SVP$</span> to <span class="math-container">$CVP$</span> <a href="https://people.csail.mit.edu/vinodv/COURSES/CSC2414-F11/L4.pdf" rel="noreferrer">https://people.csail.mit.edu/vinodv/COURSES/CSC2414-F11/L4.pdf</a>.</p>
<p>Is there a reduction in the reverse direction?</p>

<np><integer-lattice>
CVP to SVP reduction?
Turbo
# CVP to SVP reduction?

(Asked by: username_0 on 2023-06-30)

The notes here provide a reduction from $SVP$ to $CVP$ <https://people.csail.mit.edu/vinodv/COURSES/CSC2414-F11/L4.pdf>.

Is there a reduction in the reverse direction?

**Tags:** np, integer-lattice


---

## 1 answers

### Answer by username_1 on 2023-07-01. Score: 5 | Accepted answer

The short answer is "yes," but with several caveats, maybe the most important of which is that all known such reductions from CVP to SVP in the Euclidean norm are randomized. Self promotion: check out Section 3 of [my survey on SVP](https://eccc.weizmann.ac.il/report/2022/170/).

> **Comments:**
> **username_0**: I see only a reduction from GapCVP using Kannan's embedding but not from CVP to SVP.  
> **username_1**: The reductions described there are between the decision (Gap) versions of the problems (and in fact from a variant of GapCVP), but also works for the search versions. (Kannan's embedding isn't a valid reduction by itself.)  
> **username_0**: Perhaps I am new to the area and so I don't know. Isn't CVP different from GapCVP?  
> **username_1**: "Gap" just means the decision version. This is explained in the introduction!  

---

