Abstract

In this talk I will present an efficient algorithm for a central problem in quadratic Fourier analysis, and which can be seen as a quadratic generalisation of the celebrated Goildreich-Levin algorithm. More precisely, given a bounded function f on the Boolean hypercube {0, 1}ⁿ and any ε > 0, our algorithm returns a quadratic polynomial q: {0, 1}ⁿ → {0, 1} so that the correlation of f with the function (−1)^q is within an additive ε of the maximum possible correlation with a quadratic phase function. This algorithm runs in O(n³) time and makes O(n² log n) queries to f. As a corollary, we obtain an algorithmic inverse theorem for the order-3 Gowers norm with polynomial guarantees.

Our algorithm is obtained using ideas from recent work on quantum learning theory. Its construction significantly deviates from previous approaches based on algorithmic proofs of the inverse theorem for order-3 Gowers norms (and in particular does not rely on the recent resolution of the polynomial Freiman-Ruzsa conjecture).

Based on joint work with Jop Briët.

Please note that this talk will exceptionally take place in MR14 .