## 5 Approximation Algorithms for \(\mathsf{SVP}^{(p)}\) and \(\mathsf{CVP}^{(p)}\)
### Algorithm for Approximate \(\mathsf{SVP}^{(p)}\)  
We note that at the end of the sieving procedure in Algorithm 1, we obtain lattice vectors of length at most \(R^{\prime}=\frac{\xi(2-\gamma)\lambda}{1-\gamma}+O(\lambda/n)\). Thus, if we can ensure that one of the vectors obtained at the end of the sieving procedure is non-zero, we obtain a \(\tau=\frac{\xi(2-\gamma)}{1-\gamma}+o(1)\)-approximation of the shortest vector. Consider a new algorithm \(\mathcal{A}\) (let us call it Approx-SVP) that is identical to Algorithm 1, except that Step 12 is replaced by the following:  
* Find a non-zero vector \(\mathbf{v}_{0}\) in \(\{(\mathbf{y}_{i}-\mathbf{e}_{i}):(\mathbf{e}_{i},\mathbf{y}_{i})\in S\}\). We now show that if we start with sufficiently many vectors, we must obtain a non-zero vector. Lemma 11: _If \(N\geq\frac{2}{q}(k|\mathcal{C}|+1)\), then with a probability of at least \(1/2\), Algorithm \(\mathcal{A}\) outputs a non-zero vector in \(\mathcal{L}\) of a length of at most \(\frac{\xi(2-\gamma)\lambda}{1-\gamma}+O(\lambda/n)\) with respect to \(\ell_{p}\) norm._  
Proof: Of the \(N\) vector pairs \((\mathbf{e},\mathbf{y})\) sampled in steps 2-6 of Algorithm \(\mathcal{A}\), we consider those such that \(\mathbf{e}\in(D_{1}\cup D_{2})\). We have already seen there are at least \(\frac{qN}{2}\) such pairs. We remove \(|\mathcal{C}|\) vector pairs in each of the \(k\) sieve iterations. Thus, at step 12 of Algorithm 1, we have \(N^{\prime}\geq 1\) pairs \((\mathbf{e},\mathbf{y})\) to process. With a probability of \(1/2\), \(\mathbf{e}\), and hence \(\mathbf{w}=\mathbf{y}-\mathbf{e}\) is replaced by either \(\mathbf{w}+\mathbf{u}\) or \(\mathbf{w}-\mathbf{u}\). Thus, the probability that this vector is the zero vector is at most \(1/2\). We thus obtain the following result. Theorem 5: _Let \(\gamma\in(0,1)\), \(\xi>1/2\) and \(\tau=\frac{\xi(2-\gamma)}{1-\gamma}+o(1)\), Assume we are given a full-rank lattice \(\mathcal{L}\subset\mathbb{Q}^{n}\). There is a randomized algorithm that \(\tau\) approximates \(\mathsf{SVP}^{(p)}\) with a success probability of at least \(1/2\) and a space and time complexity \(2^{(c_{s}+c_{c})n+o(n)}\), where \(c_{c}=\log\left(2+\frac{2}{\gamma}\right)\), and \(c_{s}=-\log\left(0.5-\frac{1}{4\xi}\right)\)._  
Note that while presenting the above theorem, we assumed that we are using the Linear Sieve in Algorithm 1. We can also use the Mixed Sieve procedure as described in Section 4. Then, we will obtain space and time complexities of \(2^{(c_{s}+c^{(p)})n+o(n)}\) and \(2^{(c_{s}+c^{(p)}+c_{p})n+o(n)}\), respectively, where \(c^{(p)}=\log\left(2+\frac{2}{\lambda\gamma}\right)+c_{p}\) and \(c_{p}=\log(1+A)\), respectively (in the Euclidean norm, the parameters are as described in Theorem 4). _Comparison with provable approximation algorithms [30; 47; 48]_  
We have mentioned in Section 1 that [47; 48] gave approximation algorithms for lattice problems that work for all \(\ell_{p}\) norms and use the quadratic sieving procedure (as hasbeen described before). Using our notations, the space and time complexities of their approximate algorithms are \(2^{c_{space}(BN)n+o(n)}\) and \(2^{c_{time}(BN)n+o(n)}\), respectively, where  
\[c_{space}(BN) = c_{s}+c_{c}(BN)\] \[\text{and }c_{time}(BN) = c_{space}(BN)+c_{c}(BN)=c_{s}+2c_{c}(BN).\]  
The authors did not mention any explicit value of the constant in the exponent. Using the above formulae, we conclude that [47; 48] can achieve time and space complexities of \(2^{3.169n+o(n)}\) and \(2^{1.586n+o(n)}\), respectively, at parameters \(\gamma=0.99,\xi=10.001\) with a large constant approximation factor. In comparison, we can achieve a space and time complexity of \(2^{2.001n+o(n)}\) with a large constant approximation factor at the same parameters. In \(\ell_{2}\) norm, using the mixed sieving procedure, we obtain a time and space complexity of \(2^{1.73n+o(n)}\) and a large constant approximation factor at parameters \(\gamma=0.999,\xi=1\). In [30], the best running time reported is \(2^{0.802n}\) for a large approximation factor.