Sampling short lattice vectors and the closest lattice vector problem

Miklós Ajtai · Ravi Kumar · D. Sivakumar

CCC 2002

Time bound

2^{O((1 + 1/δ)n)} poly(input size)

Space bound

Exponential; no explicit leading constant recorded

Source / version date

21 May 2002

Comparison variant

Approximate search · Euclidean

Cost scale

Parameterized time bound in n and approximation factor

Norm

Euclidean ℓ₂

Approximation guarantee

1 + δ, for δ > 0

Preprocessing

Included

Success guarantee

Randomized approximation

model

Classical randomized Turing reduction to exact SVP and short-vector sampling

Assumptions and source notes

The original abstract gives a randomized (1+δ)-approximation through exact SVP and short-vector sampling. The hidden constant is left unspecified. The dependence on δ prevents interpreting this as exact CVP.

Source location

Abstract, runtime and approximation statement
Version: CCC 2002, author publication page dated 21 May 2002

Primary source ↗

@inproceedings{ajtai-kumar-sivakumar-2002,
  author = {Miklós Ajtai and Ravi Kumar and D. Sivakumar},
  title = {{Sampling short lattice vectors and the closest lattice vector problem}},
  year = {2002},
  doi = {10.1109/CCC.2002.1004339},
  url = {https://doi.org/10.1109/CCC.2002.1004339},
  keywords = {CVP, lattice algorithms},
  cr_date = {2002-05-21},
  cr_status = {published},
  cr_venue = {CCC 2002},
  cr_author_ids = {miklos-ajtai; ravi-kumar; d-sivakumar},
  howpublished = {CCC 2002}
}