On Learning Parities with Dependent Noise

Autor:	Golowich, Noah, Moitra, Ankur, Rohatgi, Dhruv
Rok vydání:	2024
Předmět:	Computer Science - Cryptography and Security Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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. Comment: This note draws heavily from arXiv:2404.03774
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2404.11325 Zobrazit plný text záznamu View this record from Arxiv