On Learning Parities with Dependent Noise

arXiv:2404.11325v1 Announce Type: new
Abstract: In this expository note we show that the learning parities with noise (LPN) assumption is robust to weak dependencies in the noise distribution of small batches of samples. This provides a partial converse to the linearization technique of [AG11]. The material in this note is drawn from a recent work by the authors [GMR24], where the robustness guarantee was a key component in a cryptographic separation between reinforcement learning and supervised learning.

arxiv cs.cr cs.ds dependencies distribution material noise partial