BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:A near-optimal quadratic Goldreich-Levin algorithm - Davi de Castr
 o Silva (University of Cambridge)
DTSTART:20250611T123000Z
DTEND:20250611T140000Z
UID:TALK232963@talks.cam.ac.uk
CONTACT:Julia Wolf
DESCRIPTION:In this talk I will present an efficient algorithm for a centr
 al problem in quadratic Fourier analysis\, and which can be seen as a quad
 ratic generalisation of the celebrated Goildreich-Levin algorithm. More pr
 ecisely\, given a bounded function f on the Boolean hypercube {0\, 1}^n^ a
 nd any ε > 0\, our algorithm returns a quadratic polynomial q: {0\, 1}^n^
  → {0\, 1} so that the correlation of f with the function (−1)^q^ is w
 ithin an additive ε of the maximum possible correlation with a quadratic 
 phase function. This algorithm runs in O(n^3^) time and makes O(n^2^ log n
 ) queries to f. As a corollary\, we obtain an algorithmic inverse theorem 
 for the order-3 Gowers norm with polynomial guarantees.\n\nOur algorithm i
 s obtained using ideas from recent work on quantum learning theory. Its co
 nstruction significantly deviates from previous approaches based on algori
 thmic proofs of the inverse theorem for order-3 Gowers norms (and in parti
 cular does not rely on the recent resolution of the polynomial Freiman-Ruz
 sa conjecture).\n \nBased on joint work with Jop Briët.\n\nPlease note th
 at this talk will exceptionally take place in MR14.
LOCATION:MR14\, CMS
END:VEVENT
END:VCALENDAR