Solving the Closest Vector Problem in 2^n Time---The Discrete Gaussian Strikes Again!

Divesh Aggarwal · Daniel Dadush · Noah Stephens-Davidowitz

FOCS 2015

Time bound

2^n+o(n) when log n log f(n)=o(n)

Space bound

At most 2^n+o(n) storage from the list algorithm

Source / version date

29 Sept 2015

Comparison variant

Classical · shifted · distance-relative width

Cost scale

2^{c n + o(n)}

Width and parameter regime

s > dist(t,L)/f(n), efficiently computable f(n) >= n^{omega(1)} and log f(n)=o(n/log n)

Output batch

At least m=rho_s(L-t)/max_{c in L/(2L)} rho_s(c-t) samples; m is instance- and width-dependent

Joint distribution error

Joint total-variation error 2^{-C n^2}, source constant C

Cost model

Randomized classical; full list preparation included; polynomial input-size factors suppressed

Assumptions and source notes

The full theorem has runtime 2^{n+O(log n log f(n))}. The coefficient 1 requires the displayed growth restriction on f; this is a cutoff sampler rather than arbitrary-width shifted DGS.

Source location

Definition 2.11; Theorem 4.7, printed pp. 14–15
Version: arXiv:1504.01995v2, 29 September 2015

Primary source ↗

@misc{paper-eb07a87a7ce7,
  author = {Divesh Aggarwal and Daniel Dadush and Noah Stephens-Davidowitz},
  title = {{Solving the Closest Vector Problem in 2^n Time---The Discrete Gaussian Strikes Again!}},
  year = {2015},
  url = {https://arxiv.org/abs/1504.01995},
  cr_date = {2015-04-08},
  cr_status = {published},
  cr_venue = {FOCS 2015},
  cr_author_ids = {divesh-aggarwal; daniel-dadush; noah-stephens-davidowitz},
  howpublished = {FOCS 2015; arXiv:1504.01995}
}