<p>Although the Goldreich-Goldwasser protocol works for any <span class="math-container">$\gamma &gt; 1$</span>, it is only <strong>efficient</strong> (i.e., it only runs in polynomial time) for sufficiently large <span class="math-container">$\gamma$</span>, specifically <span class="math-container">$\gamma \geq \Omega(\sqrt{n/\log n})$</span>. Intuitively, the reason for this (using the notation in Regev's lecture notes) is that the balls <span class="math-container">$B(0, r)$</span> and <span class="math-container">$B(v, r)$</span> may have very little overlap in the &quot;<span class="math-container">$v$</span> is close to the lattice&quot; case if <span class="math-container">$r = \gamma d/2$</span> for small <span class="math-container">$\gamma &gt; 1$</span>.</p>
<p>In recent work with many co-authors, we gave a general analysis of the Goldreich-Goldwasser protocol. See Theorem 3.1 in <a href="https://arxiv.org/abs/2211.11693" rel="nofollow noreferrer">https://arxiv.org/abs/2211.11693</a>. The protocol runs in roughly <span class="math-container">$(1 - 1/\gamma^2)^{-n/2}$</span> time, where <span class="math-container">$n$</span> is the rank of the underlying lattice and <span class="math-container">$\gamma &gt; 1$</span>. (We also generalized the protocol to non-Euclidean norms.)</p>

CC BY-SA 4.0
2023-04-19T17:53:23.527Z
2023-04-19T17:53:23.527Z
Huck Bennett
<p>In <a href="https://cims.nyu.edu/%7Eregev/teaching/lattices_fall_2004/ln/gg.pdf" rel="nofollow noreferrer">this</a> lecture Regev introduced the Goldreich-Goldwasser protocol (start of page 2) to show that <span class="math-container">$GapCVP_{\sqrt{n}} \in coAM$</span>. The protocol is really intuitive, but I don't really understand why he doesn't directly show the claim for an arbitrary <span class="math-container">$\gamma$</span> instead of <span class="math-container">$\sqrt{n}$</span>. This protocol seems to work for every <span class="math-container">$\gamma$</span> or am I wrong?</p>

<lattice>
Is $GapCVP_{\gamma} \in coAM$ for all $\gamma$?
kerf
# Is $GapCVP_{\gamma} \in coAM$ for all $\gamma$?

(Asked by: username_0 on 2023-04-19)

In [this](https://cims.nyu.edu/%7Eregev/teaching/lattices_fall_2004/ln/gg.pdf) lecture Regev introduced the Goldreich-Goldwasser protocol (start of page 2) to show that $GapCVP\_{\sqrt{n}} \in coAM$. The protocol is really intuitive, but I don't really understand why he doesn't directly show the claim for an arbitrary $\gamma$ instead of $\sqrt{n}$. This protocol seems to work for every $\gamma$ or am I wrong?

**Tags:** lattice


---

## 1 answers

### Answer by username_1 on 2023-04-19. Score: 0 | Accepted answer

Although the Goldreich-Goldwasser protocol works for any $\gamma > 1$, it is only **efficient** (i.e., it only runs in polynomial time) for sufficiently large $\gamma$, specifically $\gamma \geq \Omega(\sqrt{n/\log n})$. Intuitively, the reason for this (using the notation in Regev's lecture notes) is that the balls $B(0, r)$ and $B(v, r)$ may have very little overlap in the "$v$ is close to the lattice" case if $r = \gamma d/2$ for small $\gamma > 1$.

In recent work with many co-authors, we gave a general analysis of the Goldreich-Goldwasser protocol. See Theorem 3.1 in <https://arxiv.org/abs/2211.11693>. The protocol runs in roughly $(1 - 1/\gamma^2)^{-n/2}$ time, where $n$ is the rank of the underlying lattice and $\gamma > 1$. (We also generalized the protocol to non-Euclidean norms.)


---

