Welcome to MathOverflow

Question

5

1

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?

edited Sep 3 2010 at 2:37

Steve Huntsman
8,139●1●22●56

asked Sep 3 2010 at 0:34

dorkusmonkey
303●1●7

	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 2010 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 2010 at 20:07

Steve Huntsman · Accepted Answer · 2010-09-03 02:35:07Z UTC

5

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.

answered Sep 3 2010 at 2:35

Steve Huntsman
8,139●1●22●56

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 2010 at 11:40

felix · Answer 2 · 2010-09-03 08:39:38Z UTC

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).

Other norms for Lattice reduction techniques (LLL, PSLQ)?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.