2026-08-10T22:35:42Z https://drops.dagstuhl.de/oai

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

Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity Norm Aggarwal, Divesh Mukhopadhyay, Priyanka Lattice Shortest Vector Problem Closest Vector Problem l_infty norm Ajtai, Kumar and Sivakumar [Ajtai et al., 2001] gave the first 2^O(n) algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. The algorithm starts with N in 2^O(n) randomly chosen vectors in the lattice and employs a sieving procedure to iteratively obtain shorter vectors in the lattice, and eventually obtaining the shortest non-zero vector. The running time of the sieving procedure is quadratic in N. Subsequent works [Arvind and Joglekar, 2008; Blömer and Naewe, 2009] generalized the algorithm to other norms. We study this problem for the special but important case of the l_infty norm. We give a new sieving procedure that runs in time linear in N, thereby improving the running time of the algorithm for SVP in the l_infty norm. As in [Ajtai et al., 2002; Blömer and Naewe, 2009], we also extend this algorithm to obtain significantly faster algorithms for approximate versions of the shortest vector problem and the closest vector problem (CVP) in the l_infty norm. We also show that the heuristic sieving algorithms of Nguyen and Vidick [Nguyen and Vidick, 2008] and Wang et al. [Wang et al., 2011] can also be analyzed in the l_infty norm. The main technical contribution in this part is to calculate the expected volume of intersection of a unit ball centred at origin and another ball of a different radius centred at a uniformly random point on the boundary of the unit ball. This might be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Divesh Aggarwal and Priyanka Mukhopadhyay 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.35 urn:nbn:de:0030-drops-99837 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.35 eng https://creativecommons.org/licenses/by/3.0/legalcode