Certifying shortest vector in a lattice

[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?

 

[Dragonfall]

Typo: basics = basis

 

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

 

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

 

[Office_Shredder]

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

 

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

 

[hamster143]

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.

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

 

[Office_Shredder]

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.

Somehow I missed the integer part

 

[Dragonfall]

There's a paper where which proves that the "greedy" algorim used by Euclid and Gauss works up to dimension 4: http://www.springerlink.com/content/2r7pdhnjjbj5jefd/

I haven't read it yet. I'm curious to see why 4 dimensions is the limit.