In this work we prove a high dimensional analogue of the beloved Goldreich-Levin theorem (STOC 1989), which is the first local list-decoding algorithm. We consider the following algorithmic problem: given oracle access to a function $f: Z_q^m \rightarrow Z_q^n$ such that $\Pr_{x \sim Z_q^m} [ f(x)=Ax ] \geq \epsilon$ for some matrix $A \in Z_q^{n \times m}$ and $\epsilon>0$, recover $A$ (or a list of all such matrices).

The original Goldreich-Levin theorem (which handles the case $n=1$ above) actually handles the agreements $\epsilon \gt 1/q$ for any $n$. Hence, we focus on tiny agreements $\epsilon \leq 1/q$. As stated, this problem cannot be efficiently solved, since when the list of matrices $A$ with good agreement with $f$ might be exponentially large. Thus we define a new notion of list-decoding; a short list of such matrices "capturing'' all others.

Our main theorem gives an algorithm which efficiently recovers a (small) list, of size $O( \epsilon^{-1} )$, of linear maps $A$ which satisfy: (1) each $A$ good agreement with $f$, and (2) every linear map which has good agreement with $f$, also has good agreement with some map $A$ in our list. The proof makes novel use of Fourier analysis.

Short Bio: Silas Richelson is an Assistant Professor in the CSE Department at UC Riverside. His research interests are in Cryptography, Computer Security and Complexity Theory. He got his Ph. D. in 2014 from UCLA under the supervision of Rafail Ostrovsky. From 2015 to 2017 he was a postdoctoral researcher with a joint appointment at the MIT CSAIL and BU Computer Science departments, working with Vinod Vaikuntanathan and Ran Canetti.