Theory of Computing
-------------------
Title : Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem
Authors : Miklos Ajtai
Volume : 4
Number : 2
Pages : 21-51
URL : http://www.theoryofcomputing.org/articles/v004a002
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 (2k)^{2n/k}. (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, we prove
the existence of a basis in R^n which is K-Z-reduced on all
k-segments and where the ratio ||b_1||/shortest(L) is at
least k^{cn/k}. Noting that such a basis renders all versions
of Schnorr's algorithm idle (output = input), it follows that
the quantity k^{cn/k} is a lower bound on the approximation
ratio any version of Schnorr's algorithm can achieve on the
shortest vector problem. This proves that Schnorr's analysis
of the approximation ratio of his algorithm is optimal apart
from the constant in the exponent. We also solve an open
problem formulated by Schnorr about the Korkine-Zolotareff
lattice constants \alpha_k. We show that his upper bound
\alpha_k < k^{1+ln k} is the best possible apart from a
constant factor in the exponent. We prove a similar result
about his upper bound \beta_k <= 4k^2, where \beta_k is
another lattice constant with an important role in Schnorr's
analysis of his algorithm.