1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Certifying shortest vector in a lattice

  1. Jul 17, 2010 #1
    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. jcsd
  3. Jul 18, 2010 #2
    Typo: basics = basis
  4. Jul 19, 2010 #3
    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.
  5. Jul 19, 2010 #4
    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.
  6. Jul 19, 2010 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
  7. Jul 19, 2010 #6
    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.
  8. Jul 19, 2010 #7
    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
  9. Jul 19, 2010 #8


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Somehow I missed the integer part
  10. Jul 20, 2010 #9
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Certifying shortest vector in a lattice
  1. Lattice question (Replies: 4)