A High Dimensional Goldreich-Levin Theorem

In this work we prove a high dimensional analogue of the beloved Goldreich-Levin Theorem (STOC 1989). We consider the following algorithmic problem: given oracle access to a function f:ℤqm→ℤqn such that Prx∼ℤqm[f(x)=Ax]≥ε for some A∈ℤqn× m and ε>0, recover A (or a list of all such matrices). We focus on the case ε≤ 1/q since when ε ≥ 1/q+δ, the problem is solved by the original Goldreich-Levin Theorem. As stated, this problem cannot be efficiently solved, since when ε ≤ 1/q the list of A with good agreement with f might be exponentially large. Our main theorem gives an algorithm which efficiently recovers a list of affine maps of size (1/ε ) which have good agreement with f, and such that every linear map which has good agreement with f, also has good agreement with some affine map in our list. Our proof makes novel use of Fourier analysis. Our main theorem has applications to effective property testing.