# Algorithms for Sparse LPN and LSPN Against Low-noise

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2024.

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

- [Noise Stability of Transformer Models](https://mlsanity.com/paper/2602.08287/) (2026)

## Abstract (arXiv)

We consider sparse variants of the classical Learning Parities with random Noise (LPN) problem. Our main contribution is a new algorithmic framework that provides learning algorithms against low-noise for both Learning Sparse Parities (LSPN) problem and sparse LPN problem. Different from previous approaches for LSPN and sparse LPN, this framework has a simple structure and runs in polynomial space. Let n be the dimension, k denote the sparsity, and η be the noise rate. As a fundamental problem in computational learning theory, Learning Sparse Parities with Noise (LSPN) assumes the hidden parity is k-sparse. While a simple enumeration algorithm takes n choose k=O(n/k)k time, previously known results stills need n choose k/2 = Omega(n/k)k/2 time for any noise rate η. Our framework provides a LSPN algorithm runs in time O(η · n/k)k for any noise rate η, which improves the state-of-the-art of LSPN whenever η ∈ ( k/n,√k/n). The sparse LPN problem is closely related to the classical problem of refuting random k-CSP and has been widely used in cryptography as the hardness assumption. Different from the standard LPN, it samples random k-sparse vectors. Because the number of k-sparse vectors is n choose k<nk, sparse LPN has learning algorithms in polynomial time when m>nk/2. However, much less is known about learning algorithms for constant k like 3 and m<nk/2 samples, except the Gaussian elimination algorithm of time eη n. Our framework provides a learning algorithm in e^O(η · n^fracδ+12) time given δ ∈ (0,1) and m ≈ n^1+(1-δ)· frack-12 samples. This improves previous learning algorithms. For example, in the classical setting of k=3 and m=n1.4, our algorithm would be faster than than previous approaches for any η<n-0.7.