General Information

---

Project Description

Acknowledgements

First, thank you to my mentor Professor Sumegha Garg for guidance in this project.

This work was carried out while I was a participant in the 2024 DIMACS REU program at Rutgers University, supported by NSF grant CNS-2150186.

---

Weekly Log

Week 1:

I met with Professor Garg at the start of the program. We had previously discussed the problem statement over Zoom, and she answered a few questions I had about related works. Then she gave me more background on relevant techniques in past work, namely branching programs and extractors. We will discuss potential approaches to proving a tighter lower bound next week.

Following our meeting for the rest of the week, I spent most of my time reading the main proof of Memory-Sample Lower Bounds for Learning Parity with Noise [GKLR21], which is the paper we are jumping off from with the best memory-sample lower bound on LPN so far. I also refreshed lecture notes on information theory, which will be useful in determining how much progress an LPN learner makes toward determining the LPN secret. Finally, I created my introductory presentation.

Week 2:

This week began with practicing/giving my introductory presentation on the problem statement. It gave me the opportunity to really understand and make concise what the key ideas and techniques were in the prior work (i.e. branching programs and sufficiently low bias in the submatrices for the extractor representation of the learning problem).

Following that, I met with Prof. Garg twice and we further discussed why the extractor-based techniques in the previous work could not extend to the tighter lower bound. I gained a much better understanding of the knowledge surrounding parity learning in general. We will continue to model the learning problem as a branching program, as that is a standard model for memory-bounded programs, but will need to redefine what it means for an edge (which now corresponds to many samples rather than just one) or vertex to be "bad" or give too much information about the LPN secret. Now that an edge represents many samples, we have to consider patterns or groups of samples that may give information, rather than just one sample at a time. We came up with a possible definition for a generally bad edge, for which need to argue that there are negligible, and now the task for next week is to define a bad edge per vertex.

Week 3:

Now we are looking to define a bad edge given that we have landed on a particular vertex. The main task here is to determine what a reasonable bound for the ratio between distribution of the edge e given vertex v and the distribution of e in the whole branching program. I spent most of the week trying edges and belief distributions with different properties (repeated samples, r bits of x being known, etc) to try to gain some intuition about the quantity, and we continued this in our meeting on Friday.

If our belief distribution P_x|v is uniform, this quantity will be 1. Then we want to compute the bias of this distribution from 1 as the belief distribution changes. I tried to estimate/get intuition for the bias as H(P_x|v) varies farther from uniform. We realized that there are some patterns in x that would lead to edges with high bias with a significant likelihood, so in our meeting, we discussed placing additional restrictions on the error parameter epsilon and the edges themselves in hopes of getting around this. I also attended the CS theory reading group and listened to a paper presentation from Vihan Shah on approximation algorithms for maximum independent sets with an oracle that answers vertex membership queries.

Week 4:

After finding there are large classes of edges with relatively high average bias across LPN secret x values, we decided to attempt to bound correlations between pairs of edges on the same path in the branching program. Because this correlation between pairs of edges is a more complicated quantity, it has been difficult to get any intuition for it. This week, I have been using Python code to calculate these quantities for random pairs of edges and more structured pairs of edges to see if we can come up with tail bounds on the CDF of this correlation value.

Week 5:

The tails of the CDF plots of correlations between pairs of edges I produced ended up having tails that were far too shallow to have a meaningful or useful bound. In our meeting, we opted to instead prove a weaker tradeoff, with linear rather than exponential samples and introduced an additional parameter to hopefully make the proof easier.

Week 6:

This week we continued to work on proving the weaker memory-sample tradeoff, and tried to prove some intermediate claims. I also presented at the CS theory reading seminar this week on a topic in theoretically cryptography that I'm interested in: fully homomorphic encryption, specifically the 2013 Gentry-Sahai-Waters construction. It was a topic that I had seen in a course last year, so this was a great opportunity to both dive into the original paper and practice presenting to a broader audience.