Slide reduction, successive minima and several~applications (Q2872006)

\textit{N. Gama} and \textit{P. Q. Nguyen} [Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. Victoria, Canada, May 17--20, 2008. New York, NY: Association for Computing Machinery (ACM). 207--216 (2008; Zbl 1230.11153)] have presented slide reduction which is currently the best SVP approximation algorithm in theory. In this paper the authors prove the upper and lower bounds for the ratios \(\|b_i^{\ast}\|/\lambda_i(L)\) and \(\|b_i\|/\lambda_i(L)\), where \(b_1, \dots , b_n\) is a slide reduced basis and \(\lambda_1(L), \dots, \lambda_n(L)\) denote the successive minima of lattice \(L\). The authors define generalised slide reduction and use slide reduction to approximate i-SIVP, SMP, and CVP. In addition the paper contains the critical slide reduced basis for blocksize 2.