A near-optimal quadratic Goldreich-Levin algorithm (extended abstract)

We present a quadratic Goldreich–Levin algorithm that is nearly optimal in the following ways. Given a bounded function $f : \mathbb{F}_2^n \to \mathbb{R}$ and any $\varepsilon \gt 0$, the algorithm outputs a quadratic polynomial $q : \mathbb{F}_2^n \to \mathbb{F}_2$ whose correlation with $(-1)^q$ is within an additive $\varepsilon$ of the maximum achievable correlation with any quadratic phase function. It runs in $O_\varepsilon(n^3)$ time and makes $O_\varepsilon(n^2 \log n)$ queries to $f$, matching the information-theoretic lower bound up to a logarithmic factor. The design of our algorithm draws on ideas from recent advances in quantum learning theory and departs from previous approaches based on algorithmic proofs of the inverse theorem for the Gowers uniformity norms.