An algorithmic Polynomial Freiman-Ruzsa theorem

by Dr Davi Castro-Silva (University of Cambridge)

Friday May 8, 2026, 2:15 PM → 3:45 PM Europe/Berlin

Endenicher Allee 60, Seminarraum 0.011 (Mathezentrum)

In a major advance in additive combinatorics, Gowers, Green, Manners, and Tao resolved the long-standing Polynomial Freiman-Ruzsa (PFR) conjecture, which characterizes approximate subgroups with only polynomial loss in parameters. This result bridges combinatorial and algebraic notions of structure, and has wide-ranging implications across combinatorics and theoretical computer science.

In this talk, I will introduce the context of the PFR theorem and describe recent joint work with Jop Briët, Srinivasan Arunachalam, Arkopal Dutt, and Tom Gur, in which we develop efficient algorithms for several equivalent formulations of this theorem. A key feature of our work is the development of new bridges connecting additive combinatorics with symplectic geometry and quantum computation.

Based on the preprint arXiv:2604.04547.