2026-07-23T00:26:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8306 2024-03-06T10:30:16Z ddc:004 open_access

Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP) Aggarwal, Divesh Stephens-Davidowitz, Noah Lattices SVP CVP 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.) Schloss Dagstuhl – Leibniz-Zentrum für Informatik Divesh Aggarwal and Noah Stephens-Davidowitz 2018 Is Part Of OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SOSA.2018.12 urn:nbn:de:0030-drops-83062 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.12 eng https://creativecommons.org/licenses/by/3.0/legalcode