Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm

Divesh Aggarwal · Priyanka Mukhopadhyay

ISAAC 2018

Time bound

2^{2.82 n + o(n)}

Space bound

2^{2.82 n + o(n)}

Source / version date

15 May 2018

Comparison variant

Classical · ℓ∞ norm

Cost scale

2^{c n + o(n)}

Norm

ℓ∞

Success guarantee

At least 1/2

Computation model

Classical; polynomial input-size factors suppressed

Assumptions and source notes

Exact ℓ∞-SVP using the birthday variant, with γ = 0.67 and ξ = 0.868. The coefficient was checked in v2; the row conservatively uses that version’s 15 May 2018 arXiv date rather than assuming it was already in v1 on 8 January. It is not a Euclidean-SVP coefficient.

Source location

Theorem 3.2 and its explicit parameter specialization, PDF p. 17
Version: arXiv:1801.02358v2, 15 May 2018

Primary source ↗

@inproceedings{aggarwal-mukhopadhyay-2018-infinity,
  author = {Divesh Aggarwal and Priyanka Mukhopadhyay},
  title = {{Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm}},
  booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  year = {2018},
  url = {https://arxiv.org/abs/1801.02358},
  cr_date = {2018-01-08},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {ISAAC 2018},
  cr_author_ids = {divesh-aggarwal; priyanka-mukhopadhyay},
  note = {arXiv:1801.02358; checked version v2, 15 May 2018}
}