# Slide Reduction, Revisited---Filling the Gaps in SVP Approximation

arXiv: https://arxiv.org/abs/1908.03724 · HTML: https://mlsanity.com/paper/1908.03724/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2019.

## Built on by (most cited first, 3 of 3)

- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)

## Abstract (arXiv)

We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP). As a result, we show the fastest provably correct algorithm for δ-approximate SVP for all approximation factors n1/2+varepsilon ≤ δ ≤ nO(1). This is the range of approximation factors most relevant for cryptography.