### Our Results and Techniques
A diagrammatic representation of such a division of space in two dimensions has been given in Figure 1. It must be noted that in this figure (for ease of illustration), the radius of the small hypercube (square) is the same for \(\ell_{1},\ell_{2}\), and \(\ell_{\infty}\) balls (circles). However, in our algorithm, this radius depends on the norm. The advantage we obtain is that we can map a vector to a sub-region efficiently -in \(O(n)\) time; i.e., in a sense we obtain better \"decodability\" property. If the vector's hypercube (sub-region) does not contain a center, we select this point as the center; otherwise, we subtract this vector from the center to obtain a shorter lattice vector. Thus, the time complexity of each sieving procedure is linear in the number of sampled vectors. Overall, we obtain an improved time complexity at the cost of increased space complexity compared to previous algorithms [26; 47; 48]. A more detailed explanation can be found in Section 3.1. Specifically, we obtain the following result. Theorem 3 in Section 3.3  
Let \(\gamma\in(0,1)\), and let \(\xi>1/2\). Given a full.rank lattice \(\mathcal{L}\subset\mathbb{Q}^{n}\), there is a randomized algorithm for \(\mathsf{SVP}^{(p)}\) with a success probability of at least \(1/2\), space complexity of at most \(2^{c_{space}n+o(n)}\), and running time of at most \(2^{c_{time}n+o(n)}\), where \(c_{space}=c_{s}+\max(c_{c_{c}},c_{b}/2)\) and \(c_{time}=\max(c_{space},c_{b})\), where \(c_{c}=\log\left(2+\frac{2}{\gamma}\right)\), \(c_{s}=-\log\left(0.5-\frac{1}{4\xi}\right)\) and \(c_{b}=\log\left(1+\frac{2\xi(2-\gamma)}{1-\gamma}\right)\). A mixed sieving algorithm  
In an attempt to gain as many advantages as possible, we introduce a mixed sieving procedure (let us call it Mixed Sieve). Here, we divide a hyperball into larger hypercubes so that we can map each point efficiently to a hypercube. Within a hypercube, we perform a quadratic sieving procedure such as AKS with the vectors in that region. This improves both time and space complexity, especially in the Euclidean norm. Approximation algorithms for \(\mathsf{SVP}^{(p)}\) and \(\mathsf{CVP}^{(p)}\)We have adopted our sieving techniques to approximation algorithms for \(\mathsf{SVP}^{(p)}\) and \(\mathsf{CVP}^{(p)}\). The idea is quite similar to that described in [49] (where it was shown to work for only the \(\ell_{\infty}\) norm). In Section 5.1, we have shown that our approximation algorithms are faster than those of [47; 48], but again they require more space. Remark 1: _It is quite straightforward to extend our algorithm to the Subspace Avoiding Problem (SAP) (or Generalized Shortest Vector Problem GSVP) [47; 48]: replace the quadratic sieve by any one of the faster sieves described in this paper. We thus obtain a similar improvement in running time. By Theorem 3.4 in [47], there are polynomial time reductions from other lattice problems such as the Successive Minima Problem (SMP) (given a lattice \(\mathcal{L}\) with rank \(n\), the Successive Minima Problem (SMP) requires to find \(n\) linearly independent vectors \(\mathbf{v}_{1},\ldots,\mathbf{v}_{n}\in\mathcal{L}\) such that \(\|\mathbf{v}_{i}\|_{p}\leq c\lambda_{i}^{(p)}(\mathcal{L})\).) and Shortest Independent Vector Problem (SIVP) (given a rank \(n\) lattice \(\mathcal{L}\) the Shortest Independent Vector Problem (SIVP) requires to find \(n\) linearly independent vectors \(\mathbf{v}_{1},\ldots,\mathbf{v}_{n}\in\mathcal{L}\) such that \(\|\mathbf{v}_{i}\|_{p}\leq c\lambda_{n}^{(p)}(\mathcal{L})\). The definition of \(\lambda_{i}^{(p)}\) (and hence \(\lambda_{n}^{(p)}\)) has been given in Section 2 (Definition 5); \(c\) is the approximation factor) with approximation factor \(1+\epsilon\) to GSVP with approximation factor \(1+\epsilon\). Thus, we can obtain a similar improvement in running time for  
Figure 1: Division of the area of a circle in \(\ell_{1}\), \(\ell_{2}\), and \(\ell_{\infty}\) norm (respectively) into smaller squares. both these problems.