3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I notice that you've asked the same question on MO: mathoverflow.net/questions/37563/… 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 meta.cstheory.stackexchange.com/questions/25/… $\endgroup$ – Suresh Venkat Sep 3 '10 at 3:04
  • $\begingroup$ 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. $\endgroup$ – user834 Sep 3 '10 at 5:52
  • $\begingroup$ Answered on mathoverflow: mathoverflow.net/questions/37563/… . I'll keep it here in the hopes of getting more answers. $\endgroup$ – user834 Sep 4 '10 at 11:42
4
$\begingroup$

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

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.

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

(Thanks to @user834 for the preprint links.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.