Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice

Jeffrey C. Lagarias · Hendrik W. Lenstra, Jr. · Claus-Peter Schnorr

Combinatorica 1990

Time bound

poly(input size) query time

Space bound

Polynomial-size preprocessed bases

Source / version date

1990

Comparison variant

Approximate search · polynomial advice

Cost scale

Approximation guarantee γ(n); polynomial query time

Norm

Euclidean ℓ₂

Approximation guarantee

O(n^{3/2})

Preprocessing

Unbounded; lattice-only reciprocal KZ bases

advice

Polynomial-size collection of bases

Success guarantee

Deterministic online search

Assumptions and source notes

Reciprocal Korkin–Zolotarev bases yield the classical O(n^{3/2}) search-CVPP approximation. The original transference and closest-point bounds are in Theorem 2.7 and §6; the preprocessing interpretation is explicitly described by Regev §I and DRS §1.

Source location

Theorem 2.7 and §6; interpretation cross-checked in Regev 2004 §I and DRS 2014 §1
Version: Combinatorica 10(4), 1990

Primary source ↗

@article{lagarias-lenstra-schnorr-1990,
  author = {Jeffrey C. Lagarias and {Hendrik W. Lenstra, Jr.} and Claus-Peter Schnorr},
  title = {{Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice}},
  year = {1990},
  doi = {10.1007/BF02128669},
  url = {https://doi.org/10.1007/BF02128669},
  keywords = {CVP, lattice algorithms},
  cr_date = {1990-12-31},
  cr_date_precision = {year},
  cr_status = {published},
  cr_venue = {Combinatorica},
  cr_author_ids = {jeffrey-c-lagarias; hendrik-w-lenstra-jr; claus-peter-schnorr},
  howpublished = {Combinatorica}
}