## 4 A Mixed Sieving Algorithm  
The main advantage in dividing the space (hyperball) into hypercubes (as we did in Linear Sieve) is the efficient \"decodability\" in the sense that a vector can be mapped to a sub-region (and thus be associated with a center) in \(O(n)\) time. However, the price we pay is in space complexity, because the number of hypercubes required to cover a hyperball is greater than the number of centers required if we used smaller hyperballs like in [21; 47; 48]. To reduce the space complexity, we perform a mixed sieving procedure. Double sieving techniques have been used for heuristic algorithms as in [32], where the rough idea is the following. There are two sets of centers: the first set consists of centers of larger radius balls, and for each such center, there is another set of centers of smaller radius balls within the respective large ball. In each sieving iteration, each non-center vector is mapped to the larger balls by comparing with the centers in the first set. Then, they are mapped to a smaller ball by comparing with the second set of centers. Thus, in both levels, a quadratic sieve is applied. In our mixed sieving, the primary difference is the fact that in the two levels, we use two types of sieving methods: a linear sieve in the first level and then a quadratic sieve such as AKS in the next level. The overall outline of the algorithm is the same as in Algorithm 1, except at step 9, where we apply the following sieving procedure, which we call Mixed Sieve. An illustration is given in Figure 4.  
The input to Mixed Sieve is a set of vectors of length \(R\), and the output is a set of smaller vectors of length \(\gamma R\). 1. We divide the whole space into large hypercubes of length \(\frac{A\gamma R}{n^{1/p}}\), where \(A\) is some constant. In \(O(n)\) time, we map a vector to a large hypercube by comparing its co-ordinates. This has been explained in Section 3.1. We do not assign centers yet and do not perform any vector operation at this step. The distance between any two vectors mapped to the same hypercube is at most \(A\gamma R\) (Figure 4b). 2. Next, we perform the AKS sieving procedure within each hypercube. For each hypercube, we have a set (initially null) of centers. When a vector is mapped to a hypercube,we check if it is within distance \(\gamma R\) of any center (within that hypercube). If yes, then we subtract it from the center and add the resultant shorter vector to output set. If no, then we add this vector to the set of centers (Figure 4c). Using the same kind of counting method as in Section 3.1, we can say we need \(2^{c^{\prime}n}\) large hypercubes, where \(c^{\prime}=\log\Bigl{(}2+\frac{2}{A\gamma}\Bigr{)}\). The maximum distance between any two vectors in each hypercube is \(A\gamma R\), and we want to get vectors of length at most \(\gamma R\) by applying the AKS sieve. Thus, the number of centers (let us call these \"AKS sieve-centers\") within each hypercube is \(2^{c_{p}n+o(n)}\) where \(c_{p}=\log(1+A)\) (in the special case of Euclidean norm, we have \(c_{2}=0.401-\log\bigl{(}\frac{2}{A}\bigr{)}\)). \(c_{p}\) (and \(c_{2}\)) are obtained by applying Lemma 4. Note that the value of \(A\) must ensure the non-negativity of \(c_{2}\). Thus, the total number of centers is \(2^{c^{(p)}n+o(n)}\) where \(c^{(p)}=c^{\prime}+c_{p}\). To use the birthday paradox, we apply similar methods as given in Section 3.3 and [26]. Assume that we initially sample \(N\geq\frac{2}{q}(n^{3}k2^{c^{(p)}n+o(n)}+n2^{\frac{c_{p}}{2}n})\) vectors. Then, using similar arguments as in Section 3, we can conclude that, with high probability, we end up with the shortest vector in the lattice. We are not re-writing the proof since it is similar to that in Theorem 3. The only thing that is slightly different is the number of center pairs set aside at the beginning of the sieving iterations. As in Section 3, we randomly divide the space \(n^{3}\) times into \(2^{c^{\prime}n}\) hypercubes.