A High Dimensional Goldreich-Levin Theorem

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:Zmq⟶Znq such that Prx Zmq[f(x)=Ax] greater than or equal to ϵ for some matrix A∈Znxmq and ϵ greater than 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 ϵ greater than 1/q for any n. Hence, we focus on tiny agreements ϵ greater than or equal to 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(ϵ−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.