- Toward Lower Bounds on Memory-Sample Tradeoffs for Learning Parity with Noise
- Project Year:
2024
- REU Student (s):
Katarina Cheng | Massachusetts Institute of Technology MA
- Student 1 Institution:
Massachusetts Institute of Technology
- Project Mentor:
Sumegha Garg
- Project Mentor Area:
Computer Science
- Project Abstract:
Proving the amount of storage necessary to learn under memory-constraints has important applications to machine learning and bounded-storage cryptography. In this project, we study memory-sample tradeoffs on the learning parity with noise problem (LPN) in the streaming model. The longterm goal is to prove a lower bound on memory-sample tradeoffs for LPN of Omega(n^2/eps^2) or an exponential number of samples. n parameterizes the size of the LPN secret, while epsilon parameterizes the sample noise. In this report, we describe intermediate observations, obstacles, and results toward proving the tradeoff within our modified branching program model, similar to prior work. Finally, we provide a conjecture and some intuition toward a weaker tradeoff, which instead tolerates a polynomial number of samples.
