CVP / Provable · polynomial space

Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices

Johannes Blömer

ICALP 2000

PublishedSource checked

Time bound: n! · s^O(1)
Space bound: poly(s)

Source / version date: 2000
Comparison variant: Provable · polynomial space
Cost scale: n^{c n + o(n)}
norm: Euclidean ℓ₂
Preprocessing cost: Dual-HKZ computation included
target: Arbitrary target
Computation model: Deterministic enumeration
success: Exact output
costScale: n log₂ n

Assumptions and source notes

The publisher abstract states n! times a polynomial in input size for exact rank-n CVP. This improves the lower-order exponential factor while retaining leading coefficient 1 on the n log n scale; it is not a new smaller leading exponent.

Source location

Abstract; Kannan and Helfrich comparison; see Hanrot–Stehlé extended analysis §1 for the polynomial-space enumeration context
Version: ICALP 2000 proceedings, LNCS 1853

Selected earlier references

Selected sources cited by this paper.

Minkowski’s convex body theorem and integer programming
Ravi Kannan · 1987
Compares the n! CVP bound with the earlier enumeration algorithm. Abstract; reference 16

Primary source ↗

BibTeXDownload .bib

@inproceedings{blomer-2000,
  author = {Johannes Blömer},
  title = {{Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices}},
  year = {2000},
  doi = {10.1007/3-540-45022-X_22},
  url = {https://doi.org/10.1007/3-540-45022-X_22},
  keywords = {CVP, lattice algorithms},
  cr_date = {2000-12-31},
  cr_date_precision = {year},
  cr_status = {published},
  cr_venue = {ICALP 2000},
  cr_author_ids = {johannes-blomer},
  howpublished = {ICALP 2000}
}