9
$\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 \mathbb{Z}^n $, find a short vector s.t. $ b \in \mathbb{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$
2
  • $\begingroup$ All norms on a finite-dimensional vector space are equivalent, so a short vector in any one norm will be a (fairly) short vector in any other norm, no? $\endgroup$ Sep 3, 2010 at 3:04
  • $\begingroup$ Gerry, I think you're right about the equivalence and thus the short vector for all norms. It looks like $ \forall p, \exists r_p, R_p s.t. r_p ||x||_p \le ||x||_2 \le R_p ||x||_p $. $\endgroup$ Sep 3, 2010 at 20:07

2 Answers 2

6
$\begingroup$

The state of the art (of the possible) is covered in Khot's paper "Inapproximability Results for Computational Problems on Lattices". Here is a link to a brief section on $\ell^p$ norms.

$\endgroup$
1
  • $\begingroup$ Thank you. I think I was hoping for better algorithms with higher norms, but this is essentially saying that they're pretty much all equivalent computationally, yes? $\endgroup$ Sep 4, 2010 at 11:40
6
$\begingroup$

There is an LLL analogue for arbitrary norms; the original paper by Lovász and Scarf can be found here. I recently found a bachelor thesis1 on lattice reduction in infinity norm, which contains several other references (for example, work by Kaib and Ritter).

1Vanya Sashova Ivanova: Lattice Basis Reduction in Infinity Norm; Wayback Machine, Citeseer

$\endgroup$

Your Answer

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

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