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

Divesh Aggarwal, Noah Stephens-Davidowitz

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" sie…