## 3 A Faster Provable Sieving Algorithm in \(\ell_{p}\) Norm  
In this section, we present an algorithm for \(\mathsf{SVP}^{(p)}\) that uses the framework of the AKS algorithm [21] but uses a different sieving procedure that yields a faster running time. Using Lemma 1, we can obtain an estimate \(\lambda^{*}\) of \(\lambda_{1}^{(p)}(\mathcal{L})\) such that \(\lambda_{1}^{(p)}(\mathcal{L})\leq\lambda^{*}\leq 2^{n}\cdot\lambda_{1}^{(p) }(\mathcal{L})\). Thus, if we try polynomially many different values of \(\lambda=(1+1/n)^{-i}\lambda^{*}\), for \(i\geq 0\), then for one of them, we have \(\lambda_{1}^{(p)}(\mathcal{L})\leq\lambda\leq(1+1/n)\cdot\lambda_{1}^{(p)}( \mathcal{L})\). For the rest of this section, we assume that we know an estimated \(\lambda\) of the length of the shortest vector in \(\mathcal{L}\), which is correct up to a factor \(1+1/n\).  
The AKS algorithm (or its \(\ell_{p}\) norm generalization in [47,48]) initially uniformly samples a large number of perturbation vectors, \(\mathbf{\mathrm{e}}\in B_{n}^{(p)}(d)\), where \(d\in\mathbb{R}_{>0}\), and for each such perturbation vector, it maintains a vector \(\mathbf{y}\) close to the lattice (\(\mathbf{y}\) is such that \(\mathbf{y}-\mathbf{\mathrm{e}}\in\mathcal{L}\)). Thus, initially, we have a set \(S\) of many such pairs \((\mathbf{\mathrm{e}},\mathbf{y})\in B_{n}^{(p)}(d)\times B_{n}^{(p)}(R)\) for some \(R\in 2^{O(n)}\). The desired situation is that after a polynomial number of such sieving iterations, we are left with a set of vector pairs \((\mathbf{\mathrm{e}}^{\prime\prime},\mathbf{\mathrm{y}}^{\prime\prime})\) such that \(\mathbf{\mathrm{y}}^{\prime\prime}-\mathbf{\mathrm{e}}^{\prime\prime}\in\mathcal{L} \cap B_{n}^{(p)}(O(\lambda_{1}^{(p)}(\mathcal{L})))\). Finally, we take the pair-wise differences of the lattice vectors corresponding to these vector pairs and output the one with the smallest non-zero norm. It was shown in [21,47,48] that, with overwhelming probability, this is the shortest vector in the lattice.  
One of the main and usually the most expensive steps in this algorithm is the sieving procedure, where given a list of vector pairs \((\mathbf{\mathrm{e}},\mathbf{y})\in B_{n}^{(p)}(d)\times B_{n}^{(p)}(R)\) in each iteration, it outputs a list of vector pairs \((\mathbf{\mathrm{e}}^{\prime},\mathbf{\mathrm{y}}^{\prime})\in B_{n}^{(p)}(d)\times B _{n}^{(p)}(\gamma R)\) where \(\gamma\in\mathbb{R}_{(0,1)}\). In each sieving iteration, a number of vector pairs (usually exponential in \(n\)) are identified as \"center pairs\". The second element of each such center pair is referred to as the \"center\". By a well-defined map, each of the remaining vector pairs is associated to a \"center pair\" such that after certain operations (such as subtraction) on the vectors, we obtain a pair with a vector difference yielding a lattice vector with a norm less than \(R^{\prime}\). If we start an iteration with say \(N^{\prime}\) vector pairs and identify \(|\mathcal{C}|\) number of center pairs, then the output consists of \(N^{\prime}-|\mathcal{C}|\) vector pairs. An illustration is given in Figure 2. In [21] and most other provable variants or generalizations such as [47,48], the running time of this sieving procedure, which is the dominant part of the total running time of the algorithm, is roughly quadratic in the number of sampled vectors.  
Here, we propose a different sieving approach to reduce the overall time complexity of the algorithm. This can be thought of as a generalization of the sieving method introduced in [49] for the \(\ell_{\infty}\) norm. We divide the space such that each lattice vector can be mapped efficiently into some desired division. In the following subsection, we explain this sieving procedure, whose running time is linear in the number of sampled vectors.