2011/07/27 by Daniel Dadush, Santosh Vempala, Dadush, Daniel +1
Computer Science · Mathematics · #52C07 #68Q25 #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Privacy-Preserving Technologies in Data #cs.CC #math.FA #msc:52C07 #msc:68Q25
paper · pdf · doi:10.48550/arxiv.1107.5478
arxiv created 2011/07/27 · openalex publication_date 2011/07/27 · arxiv updated 2011/07/28 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
We give a deterministic O(log n)n algorithm for the \em Shortest Vector Problem (SVP) of a lattice under \em any norm, improving on the previous best deterministic bound of nO(n) for general norms and nearly matching the bound of 2O(n) for the standard Euclidean norm established by Micciancio and Voulgaris (STOC 2010). Our algorithm can be viewed as a derandomization of the AKS randomized sieve algorithm, which can be used to solve SVP for any norm in 2O(n) time with high probability. We use the technique of covering a convex body by ellipsoids, as introduced for lattice problems in (Dadush et al., FOCS 2011). Our main contribution is a deterministic approximation of an M-ellipsoid of any convex body. We achieve this via a convex programming formulation of the optimal ellipsoid with the objective function being an n-dimensional integral that we show can be approximated deterministically, a technique that appears to be of independent interest.