About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 2003
Conference paper
The worst-case behavior of Schnorr's algorithm approximating the shortest nonzero vector in a lattice
Abstract
Schnorr's algorithm for finding an approximation for the shortest nonzero vector in an n dimensional lattice depends on a parameter k. He proved that for a fixed k ≤ n his algorithm (block 2k-reduction) provides a lattice vector whose length is greater than the length of a shortest nonzero vector in the lattice by at most a factor of (4k2)n/k ft. (The time required by the algorithm depends on k.) We show that if k = o(n), this bound on the performance of Schnorr's algorithm cannot be improved (apart from a constant factor in the exponent), namely there is a lattice and a basis so that if they are given as an input to the algorithm then the resulting approximating factor of the output is at least kεn/k. (For larger integers k if Schnorr's algorithm runs in polynomial time then we have already a polynomial time algorithm for finding the shortest nonzero vector.) We also solve an open problem formulated by Schnorr about the the Korkine-Zolotareff lattice constants αk. We show that his upper bound αk ≤ k1+ln k is the best possible apart from a constant factor in the exponent. We prove a similar result about his upper bound βk, ≤ 4k2, where βk, is another lattice constant with an important role in Schnorr's analysis of his algorithm.