There is a secret string x about which you gradually learn some partial information. However, you have limited memory, and so can't just store all this information until it becomes enough to recover x perfectly. Given a memory bound B, how many samples (as a function of the length of x and B) do you need to recover x with high probability?

More precisely, we consider a "streaming" setting where at each step the reconstructor learns (R,M(R,x)), where R is some uniformly random string and M is some (possibly noisy) function.

In seminal work, Raz (FOCS 2016, https://arxiv.org/abs/1602.05161) considered the version of this problem where M(x,R) = <x,R>, where <.,.> denotes inner product over F_2 (the finite field of order 2) and x is a bitstring of length n. If we can store roughly n^2 bits in memory, then we can easily find x using about n samples by solving a system of linear equations. Raz showed that if the memory bound B << n^2, then exponentially many samples are required to recover x. This result was later extended to a much larger class of learning problems (STOC 2018, https://arxiv.org/abs/1708.02639).

Later work (RANDOM 2021, https://arxiv.org/abs/2107.02320, and CRYPTO 2024, https://link.springer.com/chapter/10.1007/978-3-031-68388-6_7), using analogous techniques, refined these results in the context of the "Learning Parity with Noise" (LPN) and "Learning with Errors" (LWE) problems, which are central to post-quantum cryptography. For example, LPN corresponds to the "noisy" version of Raz's original problem where the reconstructor learns samples (R, <x,R> + Noise), with Noise following a Bernoulli distribution with success probability eps. In this case, the number of required samples is exponential whenever the memory bound B is significantly smaller than n^2/eps.

Cryptographers often use variants of LPN and LWE where there is some known side information about the secret x (e.g., "entropic LWE" https://eprint.iacr.org/2020/119), or where the strings R in the samples above are not sampled uniformly at random, but rather sampled from a more structured set. The goal of this project is to understand to what extent the techniques from the works mentioned above can be adapted to obtain memory-sample bounds for these variants of LPN and LWE.