A near-optimal Quadratic Goldreich-Levin algorithm

Abstract

In this paper, we give a quadratic Goldreich-Levin algorithm that is close to optimal in the following ways. Given a bounded function $f$ on the Boolean hypercube ${\mathbb{F}}_2^n$ and any $\epsilon >0$, the algorithm returns a quadratic polynomial $q:{\mathbb{F}}_2^n\to {\mathbb{F}}_2$ so that the correlation of $f$ with the function $(-1{)}^q$ is within an additive $\epsilon$ of the maximum possible correlation with a quadratic phase function. The algorithm runs in $O_{\epsilon }(n^3)$ time and makes $O_{\epsilon }(n^2\log n)$ queries to $f$, which matches the information-theoretic lower bound of $\hat{I}\text{c◯}(n^2)$ queries up to a logarithmic factor. As a result, we obtain a number of corollaries: - A near-optimal self-corrector of quadratic Reed-Muller codes, which makes $O_{\epsilon }(n^2\log n)$ queries to a Boolean function $f$ and returns a quadratic polynomial $q$ whose relative Hamming distance to $f$ is within $\epsilon$ of the minimum distance. - An algorithmic polynomial inverse theorem for the order-3 Gowers uniformity norm. - An algorithm that makes a polynomial number of queries to a bounded function $f$ and decomposes $f$ as a sum of poly$(1/\epsilon )$ quadratic phase functions and error terms of order $\epsilon$. Our algorithm is obtained using ideas from recent work on quantum learning theory. Its construction deviates from previous approaches based on algorithmic proofs of the inverse theorem for the order-3 uniformity norm (and in particular does not rely on the recent resolution of the polynomial Fre\uıman-Ruzsa conjecture).

37 pages, 1 figure