<p>Following the specific reference provided by Steve Huntsman in his MO answer leads to the paper</p>

<ul>
<li>Oded Regev and Ricky Rosen. <em>Lattice problems and norm embeddings</em>, STOC 2006.  doi: <a href="http://doi.acm.org/10.1145/1132516.1132581" rel="nofollow">10.1145/1132516.1132581</a> (<a href="http://www.cs.tau.ac.il/~odedr/papers/lpnorm.pdf" rel="nofollow">full preprint version</a>)</li>
</ul>

<p>This paper presents randomized reductions from the approximation versions of lattice problems in the $\ell_2$ norm to any norm $\ell_p$ where $1 \le p \le \infty$.  The reductions don't quite preserve the approximation ratio, but the loss can be bounded by a factor of $(1+\epsilon)$.  So the $\ell_2$ norm yields in some sense the "easiest" versions of lattice problems.  It is enough to prove hardness of approximation using the $\ell_2$ norm, and hardness of approximation for any other $\ell_p$ norm follows with only a $(1+\epsilon)$ larger approximation factor.</p>

<p>Regev and Rosen then go on to use this to strengthen some existing hardness results.</p>

<p>On the other hand, Chris Peikert showed that lattice problems posed using $\ell_p$ norms are not substantially harder than problems posed in the $\ell_2$ norm.</p>

<ul>
<li>Chris Peikert, <em>Limits on the hardness of lattice problems in $\ell_p$ norms</em>, Computational Complexity <strong>17</strong> 300–351, 2008.  doi: <a href="http://dx.doi.org/10.1007/s00037-008-0251-3" rel="nofollow">10.1007/s00037-008-0251-3</a> (<a href="http://www.cc.gatech.edu/~cpeikert/pubs/lp_norms.pdf" rel="nofollow">full preprint version</a>)</li>
</ul>

<p>So yes, the question is sensible, and it has also essentially been answered.</p>

<p>(Thanks to @user834 for the preprint links.)</p>

CC BY-SA 3.0
2010-11-11T12:25:28.953Z
2011-04-16T10:56:57.950Z
2011-04-16T10:56:57.950Z
András Salamon
<p>LLL and other lattice reduction techniques (such as PSLQ) try to find a short basis vector relative to the 2-norm, i.e. for a given basis that has $ \varepsilon $ as its shortest vector, $ \varepsilon \in Z^n $, find a short vector s.t. $ b \in Z^n, ||b||_2 &lt; ||c^n \varepsilon||_2 $.</p>

<p>Has there been any work done to find short vectors based on other, potentially higher, norms?  Is this a meaningful question?</p>

CC BY-SA 2.5
2010-09-03T03:04:07.230Z
I notice that you've asked the same question on MO:  http://mathoverflow.net/questions/37563/other-norms-for-lattice-reduction-techniques-lll-pslq 

While crossposting is fine in general, it would be helpful to post on one site and wait for a bit before crossposting, especially since it appears that you've got your answer already on MO. 

Also see http://meta.cstheory.stackexchange.com/questions/25/material-to-supplement-the-faq/36#36
Suresh Venkat
CC BY-SA 2.5
2010-09-03T05:52:44.083Z
Sorry about this, was a little eager to hear the answer, so I thought I would maximize my chances and cross post.  I'll make sure to give a little time between cross posting next time.
user834
CC BY-SA 2.5
2010-09-04T11:42:37.323Z
Answered on mathoverflow: http://mathoverflow.net/questions/37563/other-norms-for-lattice-reduction-techniques-lll-pslq . I'll keep it here in the hopes of getting more answers.
user834
<ds.algorithms>
Other norms for Lattice reduction techniques (LLL, PSLQ)?
user834
# Other norms for Lattice reduction techniques (LLL, PSLQ)?

(Asked by: username_0 on 2010-09-03)

LLL and other lattice reduction techniques (such as PSLQ) try to find a short basis vector relative to the 2-norm, i.e. for a given basis that has $ \varepsilon $ as its shortest vector, $ \varepsilon \in Z^n $, find a short vector s.t. $ b \in Z^n, ||b||\_2 < ||c^n \varepsilon||\_2 $.

Has there been any work done to find short vectors based on other, potentially higher, norms? Is this a meaningful question?

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: I notice that you've asked the same question on MO:  http://mathoverflow.net/questions/37563/other-norms-for-lattice-reduction-techniques-lll-pslq   While crossposting is fine in general, it would be helpful to post on one site and wait for a bit before crossposting, especially since it appears that you've got your answer already on MO.   Also see http://meta.cstheory.stackexchange.com/questions/25/material-to-supplement-the-faq/36#36  
> **username_0**: Sorry about this, was a little eager to hear the answer, so I thought I would maximize my chances and cross post.  I'll make sure to give a little time between cross posting next time.  
> **username_0**: Answered on mathoverflow: http://mathoverflow.net/questions/37563/other-norms-for-lattice-reduction-techniques-lll-pslq . I'll keep it here in the hopes of getting more answers.  

---

## 1 answers

### Answer by username_2 on 2010-11-11. Score: 4 | Accepted answer

Following the specific reference provided by Steve Huntsman in his MO answer leads to the paper

* Oded Regev and Ricky Rosen. *Lattice problems and norm embeddings*, STOC 2006. doi: [10.1145/1132516.1132581](http://doi.acm.org/10.1145/1132516.1132581) ([full preprint version](http://www.cs.tau.ac.il/~odedr/papers/lpnorm.pdf))

This paper presents randomized reductions from the approximation versions of lattice problems in the $\ell\_2$ norm to any norm $\ell\_p$ where $1 \le p \le \infty$. The reductions don't quite preserve the approximation ratio, but the loss can be bounded by a factor of $(1+\epsilon)$. So the $\ell\_2$ norm yields in some sense the "easiest" versions of lattice problems. It is enough to prove hardness of approximation using the $\ell\_2$ norm, and hardness of approximation for any other $\ell\_p$ norm follows with only a $(1+\epsilon)$ larger approximation factor.

Regev and Rosen then go on to use this to strengthen some existing hardness results.

On the other hand, Chris Peikert showed that lattice problems posed using $\ell\_p$ norms are not substantially harder than problems posed in the $\ell\_2$ norm.

* Chris Peikert, *Limits on the hardness of lattice problems in $\ell\_p$ norms*, Computational Complexity **17** 300–351, 2008. doi: [10.1007/s00037-008-0251-3](http://dx.doi.org/10.1007/s00037-008-0251-3) ([full preprint version](http://www.cc.gatech.edu/~cpeikert/pubs/lp_norms.pdf))

So yes, the question is sensible, and it has also essentially been answered.

(Thanks to @user834 for the preprint links.)


---

