Question about the definition of the CVP as an approximation variant

P_Gate

10/23/23, 9:46 AM

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?

0 + 1

lattice-crypto

Mark

10/24/23, 5:10 AM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Question about the definition of the CVP as an approximation variant

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.