2 papers
cs.CR2025
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…
cs.DS2024
Revisit the Partial Coloring Method: Prefix Spencer and Sampling
Dongrun Cai, Xue Chen, Wenxuan Shu +2
As the most powerful tool in discrepancy theory, the partial coloring method has wide applications in many problems including the Beck-Fiala problem and Spencer's celebrated result…