Computer Science/Discrete Mathematics Seminar I

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 \longrightarrow Z_q^n$ such that $Pr_{x ~ Z_q^m} [ f(x)=Ax ] \geq \epsilon$ for some matrix $A \in Z_q^{n x 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.