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?

Improve this 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$
    – Gerry Myerson
    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$
    – dorkusmonkey
    Sep 3, 2010 at 20:07

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – dorkusmonkey
    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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .