Algorithms for Sparse LPN and LSPN Against Low-noise

Xue Chen, Wenxuan Shu, Zhaienhe Zhou

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 algorith…