Improved Algorithms For The Approximate K-List Problem In Euclidean Norm

We present an algorithm for the approximate k-List problem for the Euclidean distance that improves upon the Bai-Laarhoven-Stehle (BLS) algorithm from ANTS'16. The improvement stems from the observation that almost all the solutions to the approximate k-List problem form a particular configuration in n-dimensional space. Due to special properties of configurations, it is much easier to verify whether a k-tuple forms a configuration rather than checking whether it gives a solution to the k-List problem. Thus, phrasing the k-List problem as a problem of finding such configurations immediately gives a better algorithm. Furthermore, the search for configurations can be sped up using techniques from Locality-Sensitive Hashing (LSH). Stated in terms of configuration-search, our LSH-like algorithm offers a broader picture on previous LSH algorithms.For the Shortest Vector Problem, our configuration-search algorithm results in an exponential improvement for memory-efficient sieving algorithms. For k = 3, it allows us to bring down the complexity of the BLS sieve algorithm on an n-dimensional lattice from 2(0.4812n+o(n)) to 2(0.3962n+o(n)) with the same space requirement 2(0.1887n+o(n)). Note that our algorithm beats the Gauss Sieve algorithm with time resp. space of 2(0.415n+o(n)) resp. 2(0.208n+o(n)), while being easy to implement. Using LSH techniques, we can further reduce the time complexity down to 2(0.3717n+o(n)) while retaining a memory complexity of 2(0.1887n+o(n)).