Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  Gerry Myerson Sep 3 '10 at 3:04
    
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 $. –  dorkusmonkey Sep 3 '10 at 20:07
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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? –  dorkusmonkey Sep 4 '10 at 11:40
add comment

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 thesis on lattice reduction in infinity norm, which contains several other references (for example, work by Kaib and Ritter).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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