Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP)

Divesh Aggarwal · Noah Stephens-Davidowitz

SOSA 2018

Time bound

2^{1 n + o(n)}

Space bound

2^{1 n + o(n)}

Source / version date

5 Sept 2017

Comparison variant

Classical · worst case

Cost scale

2^{c n + o(n)}

Norm

Euclidean ℓ₂

Success guarantee

Randomized exact-SVP guarantee stated by the source

Computation model

Classical; polynomial input-size factors suppressed

Assumptions and source notes

A simpler exact-SVP algorithm with the same leading time and space as ADRS15. The abstract explicitly removes a rejection-sampling step from ADRS. This is an equal-exponent algorithmic milestone; it does not lower the standing exponent below 1. The paper’s approximate-CVP statement has its own regime and is not used as an exact-SVP assumption.

Source location

Abstract and submission history
Version: arXiv:1709.01535v1, 5 September 2017

Primary source ↗

@inproceedings{aggarwal-stephens-davidowitz-2017-average,
  author = {Divesh Aggarwal and Noah Stephens-Davidowitz},
  title = {{Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP)}},
  booktitle = {Symposium on Simplicity in Algorithms (SOSA 2018)},
  year = {2018},
  url = {https://arxiv.org/abs/1709.01535},
  cr_date = {2017-09-05},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {SOSA 2018},
  cr_author_ids = {divesh-aggarwal; noah-stephens-davidowitz},
  note = {arXiv:1709.01535, first submitted 5 September 2017}
}