0
$\begingroup$

I have a question about the definition of the (Closest Vector Problem) CVP. In the literature you can find for example this definition of the approximation variant of CVP:

$CVP_\gamma$, Search: Given a basis $B \in \mathbb{Z}^{m \times n}$ and a point $t \in \mathbb{Z}^m$, find a point $x \in \mathcal{L}(B)$ such that $\forall y \in \mathcal{L}(B)$,$||x-t|| \leq \gamma|| y-t ||$

Question:

My question is now and unfortunately this is a bit misleading, since some authors define $t$ as an element of $\mathbb{R}^m$. What are the arguments that speak for using $t \in \mathbb{Z}^m$ in the definition for the CSV instead of $t \in \mathbb{R}^m$?

In the hope that I have not formulated my question too unclearly, I would be interested in what you think of it?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This is perhaps a pedantic point, but one can efficiently represent $t\in\mathbb{Z}^m$ with $\approx m\log_2 \lVert t\rVert_\infty$ bits, while it is not clear you can represent an arbitrary point $t\in\mathbb{R}^m$. Of course, one can always simply choose a good-enough fixed-point approximation of $t\approx \tilde{t}\in\frac{1}{2^k}\mathbb{Z}^m$, hence why this mostly pedantic. $\endgroup$
    – Mark
    Oct 24, 2022 at 5:10

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.