• 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  
• Project Mentor (s) : Sumegha Garg - 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.