# Practically Solving LPN in High Noise Regimes Faster Using Neural Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 46 references that are in the map.
- First posted on arXiv 14 Mar 2023.

## Builds on (most cited first, 9 of 9)

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [Deep Learning Methods for Improved Decoding of Linear Codes](https://mlsanity.com/paper/1706.07043/) (2017)
- [Deep Learning for Decoding of Linear Codes - A Syndrome-Based Approach](https://mlsanity.com/paper/1802.04741/) (2018)
- [SALSA: Attacking Lattice Cryptography with Transformers](https://mlsanity.com/paper/2207.04785/) (2022)
- [Poly-time universality and limitations of deep learning](https://mlsanity.com/paper/2001.02992/) (2020)

## Abstract (arXiv)

We conduct a systematic study of solving the learning parity with noise problem (LPN) using neural networks. Our main contribution is designing families of two-layer neural networks that practically outperform classical algorithms in high-noise, low-dimension regimes. We consider three settings where the numbers of LPN samples are abundant, very limited, and in between. In each setting we provide neural network models that solve LPN as fast as possible. For some settings we are also able to provide theories that explain the rationale of the design of our models. Comparing with the previous experiments of Esser, Kubler, and May (CRYPTO 2017), for dimension n = 26, noise rate τ = 0.498, the ''Guess-then-Gaussian-elimination'' algorithm takes 3.12 days on 64 CPU cores, whereas our neural network algorithm takes 66 minutes on 8 GPUs. Our algorithm can also be plugged into the hybrid algorithms for solving middle or large dimension LPN instances.