A near-optimal quadratic Goldreich-Levin algorithm

Add to your list(s) Download to your calendar using vCal

• Davi de Castro Silva (University of Cambridge)
• Wednesday 11 June 2025, 13:30-15:00
• MR14, CMS.

If you have a question about this talk, please contact Julia Wolf.

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 .

This talk is part of the Discrete Analysis Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Discrete Analysis Seminar
• Hanchen DaDaDash
• Interested Talks
• MR14, CMS
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.