# Certifying shortest vector in a lattice

1. Jul 17, 2010

### Dragonfall

Given an n dimensional integer lattice, is it possible to certify a vector as being a shortest one in time polynomial in n?

If we then fix the dimension n, is it possible to certify the shortest-ness in time strictly less than O(k^n) where k is the length of the largest basics vector?

2. Jul 18, 2010

### Dragonfall

Typo: basics = basis

3. Jul 19, 2010

### hamster143

The first half seems to be a difficult problem. In a general case of a non-integer lattice, all that is known is that the problem of finding the shortest vector is NP-hard, so, it is not currently known whether there's a method to verify a solution in polynomial time. And, unless you place a limit the length of basis vectors, there's no reason to expect that "integerness" would let you reduce complexity.

4. Jul 19, 2010

### Dragonfall

What about the second part? In 2 dimensions, Gauss' basis reduction runs in linear time (I think), and finds the shortest vector. In higher dimensions I've yet to see something similar.

5. Jul 19, 2010

### Office_Shredder

Staff Emeritus
I would be surprised if the algorithm time relied on the length of the longest basis vector. Otherwise you could just scale your lattice by a factor of a thousand, run your algorithm super fast, then multiply the resulting vector by 1000. Unless I'm missing something

6. Jul 19, 2010

### Dragonfall

Since we're talking about integer lattices, you can't scale arbitrarily. Even if we're talking about rational lattices, scaling does not change the amount of bits necessary to represent a vector. Unless I misunderstood you.

7. Jul 19, 2010

### hamster143

There is an algorithm to solve the whole problem exactly in 2^O(n) time: M. Ajtai, R. Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem, 2001. 2^O(n) is strictly less than O(k^n), if I'm not mistaken.

Edit: less for large enough k. The original paper by Ajtai & co. does not quantify the multiplier in O(n).

I don't understand any of the proofs or algorithms nearly well enough to adopt them to the specific task at hand... I wonder what it would mean to solve the problem rigorously as originally posited in the thread? Probably at least a publishable paper; not enough for a PhD thesis...

Last edited: Jul 20, 2010
8. Jul 19, 2010

### Office_Shredder

Staff Emeritus
Somehow I missed the integer part

9. Jul 20, 2010