@inproceedings{ASJustTake18,
  title = {Just take the average! An embarrassingly simple $2^n$-time algorithm for SVP (and CVP)},
  abstract = {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.)},
  url = {http://arxiv.org/abs/1709.01535},
  booktitle = {SOSA},
  author = {Aggarwal, Divesh and {Stephens-Davidowitz}, Noah},
  year = {2018}
}

{"_id":"23PbGvxw9wFhPCjxi","bibbaseid":"aggarwal-stephensdavidowitz-justtaketheaverageanembarrassinglysimple2ntimealgorithmforsvpandcvp-2018","authorIDs":["NsKfZS8svvuZwZEBa"],"author_short":["Aggarwal, D.","Stephens-Davidowitz, N."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Just take the average! An embarrassingly simple $2^n$-time algorithm for SVP (and CVP)","abstract":"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 $γ$-approximate CVP for any $γ = 1+2^{-o(n/łog 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.)","url":"http://arxiv.org/abs/1709.01535","booktitle":"SOSA","author":[{"propositions":[],"lastnames":["Aggarwal"],"firstnames":["Divesh"],"suffixes":[]},{"propositions":[],"lastnames":["Stephens-Davidowitz"],"firstnames":["Noah"],"suffixes":[]}],"year":"2018","bibtex":"@inproceedings{ASJustTake18,\n title = {Just take the average! An embarrassingly simple $2^n$-time algorithm for SVP (and CVP)},\n abstract = {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.)},\n url = {http://arxiv.org/abs/1709.01535},\n booktitle = {SOSA},\n author = {Aggarwal, Divesh and {Stephens-Davidowitz}, Noah},\n year = {2018}\n}\n\n\n","author_short":["Aggarwal, D.","Stephens-Davidowitz, N."],"key":"ASJustTake18","id":"ASJustTake18","bibbaseid":"aggarwal-stephensdavidowitz-justtaketheaverageanembarrassinglysimple2ntimealgorithmforsvpandcvp-2018","role":"author","urls":{"Paper":"http://arxiv.org/abs/1709.01535"},"metadata":{"authorlinks":{"stephens-davidowitz, n":"https://www.noahsd.com/"}},"downloads":58},"bibtype":"inproceedings","biburl":"https://dl.dropboxusercontent.com/s/fdsagwnpu86ikr5/bibbase_published.bib","creationDate":"2020-12-14T08:01:23.334Z","downloads":58,"keywords":[],"search_terms":["take","average","embarrassingly","simple","time","algorithm","svp","cvp","aggarwal","stephens-davidowitz"],"title":"Just take the average! An embarrassingly simple $2^n$-time algorithm for SVP (and CVP)","year":2018,"dataSources":["j49aoDnSSLjzndmof","kxAEBDHXGfX8ATRE5","HhrFT8C8XJdJggbxX","DFNYHMG5naiXCbQWf","t7S757akkuDKXd4Lt","bNuEGB6D6ArYKZG7X","rNfpY7KpfzEnPHFDu"]}