Proceedings of STOC '08
(May 17 - 20),
C. Dwork (Ed.), ACM.
Abstract:
The celebrated Lenstra-Lenstra-Lovasz lattice basis reduction algorithm
(LLL) can naturally be viewed as an algorithmic version of Hermite's
inequality on Hermite's constant. We present a polynomial-time blockwise
reduction algorithm based on duality which can similarly be viewed
as an algorithmic version of Mordell's inequality on Hermite's constant.
This achieves a better and more natural approximation factor for the
shortest vector problem than Schnorr's algorithm and its transference
variant by Gama, Howgrave-Graham, Koy and Nguyen. Furthermore, we show that this approximation
factor is essentially tight in the worst case.
Bibtex:
@inproceedings{GaNg08b,
author = {N. Gama and
P. Q. Nguyen},
title = {Finding Short Lattice Vectors within {M}ordell's Inequality},
booktitle = {STOC '08 -- Proc. 40th ACM Symposium on the Theory of Computing},
year = {2008},
publisher = {ACM}
}