  We show a $2^{n+o(n)}$-time (and space) algorithm for the Shortest Vector
Problem on lattices (SVP) that works by repeatedly running an embarrassingly
simple "pair and average" sieving-like procedure on a list of lattice vectors.
This matches the running time (and space) of the current fastest known
algorithm, due to Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS, in
STOC, 2015), with a far simpler algorithm. Our algorithm is in fact a
modification of the ADRS algorithm, with a certain careful rejection sampling
step removed.
  The correctness of our algorithm follows from a more general "meta-theorem,"
showing that such rejection sampling steps are unnecessary for a certain class
of algorithms and use cases. In particular, this also applies to the related
$2^{n + o(n)}$-time algorithm for the Closest Vector Problem (CVP), due to
Aggarwal, Dadush, and Stephens-Davidowitz (ADS, in FOCS, 2015), yielding a
similar embarrassingly simple algorithm for $\gamma$-approximate CVP for any
$\gamma = 1+2^{-o(n/\log n)}$. (We can also remove the rejection sampling
procedure from the $2^{n+o(n)}$-time ADS algorithm for exact CVP, but the
resulting algorithm is still quite complicated.)
