Block Korkin-Zolotarev Bases and Successive Minima

TitleBlock Korkin-Zolotarev Bases and Successive Minima
Publication TypeTechnical Report
Year of Publication1992
AuthorsSchnorr, C. P.
Other Numbers768

Using block Korkin–Zolotarev bases we improve Babai's construction of a nearby lattice point. Given a block Korkin–Zolotarev basis with block size beta of the lattice L and given a point x in the span of L, a lattice point v can be found in time ?^{O?} satisfying |x-v|^2 less then or equal to m ?^{2m/{?-1}_? min_u epsilon L} |x-u|. These results also bear improvements for the method of solving integer programming problems via basis reduction.

Bibliographic Notes

ICSI Technical Report tr-92-063

Abbreviated Authors

C. P. Schnorr

ICSI Publication Type

Technical Report