On Learning Parities with Dependent Noise
<|reference_start|>On Learning Parities with Dependent Noise: 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.<|reference_end|>
@article{golowich2024on,
    title={On Learning Parities with Dependent Noise},
    author={Noah Golowich, Ankur Moitra, Dhruv Rohatgi},
    journal={arXiv preprint arXiv:2404.11325},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.11325},
    primaryClass={cs.CR cs.DS}
}