Algorithms for Sparse LPN and LSPN Against Low-noise (extended abstract)

Xue Chen, Wenxuan Shu, Zhaienhe ZhouCOLT 2025

TL;DR

This paper introduces a novel algorithmic framework for efficiently learning sparse variants of the "Learning Parities with Noise" (LPN) problem, even with low noise levels. This new approach offers significant speedups over previous methods, making these computationally hard problems more tractable for practical applications and theoretical analysis.

What Problem Does This Paper Address?

The paper tackles two related problems in computational learning theory: Learning Sparse Parities with Noise (LSPN) and sparse LPN. At their core, these problems involve learning a hidden "parity" function (essentially a linear combination of bits) from noisy examples. The "sparse" aspect means the parity function depends on only a few input bits (the sparsity parameter k), making it potentially easier to learn than a dense function.

The challenge lies in the "noise" – each output label is flipped with a small probability η. While standard LPN has been extensively studied, its sparse variants, especially under low noise conditions, have remained computationally challenging. Existing algorithms for LSPN and sparse LPN often rely on complex techniques like fast matrix multiplication or tensor methods, and their performance degrades significantly with low noise. The authors aim to develop simpler, more efficient algorithms that perform well even when the noise rate η is small.

Methods

The paper's main contribution is a new, unified algorithmic framework. Unlike previous approaches that might use sophisticated matrix or tensor operations, this framework is designed to be structurally simple and implementable in polynomial space. The details of the framework are not fully elaborated in this extended abstract, but it's highlighted that the algorithms are easy to implement and avoid computationally expensive methods.

For LSPN, the proposed algorithm achieves a runtime of $O(\eta \cdot n/k)^k$, which is a significant improvement over prior results that required at least $\Omega((n/k)^{k/2})$ time. This speedup is particularly impactful when the noise rate $\eta$ is in the range $(k/n, \sqrt{k/n})$.

For sparse LPN, the framework provides a learning algorithm with a runtime of $e^{O(m^{1-\delta})}$ for $m = \max\{1, 2^{1/\delta}\} \cdot n^{1+(1-\delta)}$ samples, where $\delta \in (0, 1)$. This offers a substantial improvement over existing algorithms, especially for scenarios with a constant k (like k=3) and a limited number of samples ($m < nk/2$).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unified Framework for Sparse Problems: The paper presents a single algorithmic framework that effectively addresses both LSPN and sparse LPN, suggesting a common underlying structure or technique that can be leveraged for both.
  • Simplicity and Efficiency: A key design principle is to achieve efficiency without resorting to complex, hard-to-implement methods like fast matrix multiplication or tensor methods. This makes the algorithms more practical.
  • Improved Low-Noise Performance: The framework demonstrates significant performance gains specifically in the low-noise regime, which has been a bottleneck for previous algorithms. This is crucial for many real-world applications where noise is inherent but not overwhelming.
  • Bridging Theory and Practice: By offering simpler and faster algorithms, the work makes these theoretically important problems more accessible for both further theoretical study and potential practical implementation in areas like cryptography.

Key Results

  • LSPN: The paper provides an algorithm with a runtime of $O(\eta \cdot n/k)^k$, improving upon previous $\Omega((n/k)^{k/2})$ lower bounds for any noise rate $\eta$. This is particularly advantageous when $\eta \in (k/n, \sqrt{k/n})$.
  • Sparse LPN: A new learning algorithm is presented with a runtime of $e^{O(m^{1-\delta})}$ for a specific sample complexity $m$. For instance, in the case of $k=3$ and $m=n^{1.4}$ samples, the algorithm is faster than previous approaches for any noise rate $\eta < n^{-0.7}$.

Limitations and Future Work

The paper is an extended abstract, meaning the full details of the algorithmic framework and proofs are not presented. This limits a deep dive into the specific techniques used. The authors suggest that their framework is easy to implement, but the practical performance and scalability of these new algorithms would require further empirical evaluation. Future work would likely involve a full exposition of the algorithms, detailed complexity analyses, and exploration of their applicability to other related learning problems or cryptographic constructions.

Summary updated

BibTeX
@inproceedings{chen2025algorithms,
  author = {Xue Chen and Wenxuan Shu and Zhaienhe Zhou},
  title = {{Algorithms for Sparse LPN and LSPN Against Low-noise (extended abstract)}},
  booktitle = {Conference on Learning Theory},
  year = {2025},
}
Figure