### Our Results and Techniques  
In this paper, we adopt the framework of [21; 45] and give sieving algorithms for \(\mathsf{SVP}\) and \(\mathsf{CVP}\) in \(\ell_{p}\) norm for \(1\leq p\leq\infty\). The primary difference between our sieving algorithm and the previous AKS-style algorithms such as those in [21; 45; 47; 48] is in the sieving procedure--ours is a linear sieve, while theirs is a quadratic sieve. This results in an improvement in the overall running time. Before describing our idea, we give an informal description of the sieving procedure of [21; 45; 47; 48]. The algorithm starts by randomly generating a set \(S\) of \(N=2^{O(n)}\) lattice vectors with a length of at most \(R=2^{O(n)}\). It then runs a sieving procedure a polynomial number of times. In the \(i\)th iteration, the algorithm starts with a list \(S\) of lattice vectors of a length of at most \(R_{i-1}\approx\gamma^{i-1}R\), for some parameter \(\gamma\in(0,1)\). The algorithm maintains and updates a list of \"centers\" \(C\), which is initialized to be the empty set. Then, for each lattice vector \(\mathbf{y}\) in the list, the algorithm checks whether there is a center \(\mathbf{c}\) at a distance of at most \(\gamma\cdot R_{i-1}\) from this vector. If there exists such a center, then the vector \(\mathbf{y}\) is replaced in the list by \(\mathbf{y}-\mathbf{c}\), and otherwise it is deleted from \(S\) and added to \(C\). This results in \(N_{i-1}-|C|\) lattice vectors which have a length of at most \(R_{i}\approx\gamma R_{i-1}\), where \(N_{i-1}\) is the number of lattice vectors at the end of \(i-1\) sieving iterations. We would like to mention here that this description hides many details and in particular, in order to show that this algorithm succeeds eventually in obtaining the shortest vector, we need to add a small perturbation to the lattice vectors to start with. The details of this can be found in Section 3. A crucial step in this algorithm is to find a vector \(\mathbf{c}\) from the list of centers that is close to \(\mathbf{y}\). This problem is called the nearest neighbor search (NNS) problem and has been well studied, especially in the context of heuristic algorithms for \(\mathsf{SVP}\) (see [33] and the references therein). A trivial bound on the running time for this is \(|S|\cdot|C|\), but much effort has been dedicated to improving this bound under heuristic assumptions (see Section 1.1.1 for some references). Since they require heuristic assumptions, such improved algorithms for the NNS have not been used to improve the provable algorithms for \(\mathsf{SVP}\). One can also view such sieving procedures as a division of the \"ambient\" geometric space (consisting of all the vectors in the current list). In the \(i\)th iteration, the space of all vectors with a length of at most \(R_{i-1}\) is divided into a number of sub-regions such that in each sub-region the vectors are within a distance of at most \(\gamma R_{i-1}\) from a center. In the previous provable sieving algorithms such as those in [21; 27; 47; 48] or even the heuristic ones, these sub-regions have been an \(\ell_{p}\) ball of certain radius (if the algorithm is in \(\ell_{p}\) norm) or some sections of it (spherical cap, etc.). Given a vector, one has to compare it with all the centers (and hence sub-regions formed so far) to determine in which of these sub-regions it belongs. If none is found, we make it a center and associate a new sub-region with it. Note that such a division of space depends on the order in which the vectors are processed. The basic idea behind our sieving procedure (let us call it Linear Sieve) is similar to that used in [49] in the special case of the \(\ell_{\infty}\) norm. In fact, our procedure is a generalization of this method for all \(\ell_{p}\) norm (\(1\leq p\leq\infty\)). We select these sub-regions as hypercubes and divide the ambient geometric space a priori (before we start processing the vectors in the current list) considering only the maximum length of a vector in the list.