2026/04/06 by Davi Castro-Silva, Jop Briët, Srinivasan Arunachalam +2 · 1 voice
#math.CO #cs.DS
We provide algorithmic versions of the Polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Ann. of Math., 2025). In particular, we give a polynomial-time algorithm that, given a set A ⊆ \mathbbF2n with doubling constant K, returns a subspace V ⊆ \mathbbF2n of size |V| ≤ |A| such that A can be covered by 2KC translates of V, for a universal constant C>1. We also provide efficient algorithms for several "equivalent" formulations of the Polynomial Freiman-Ruzsa theorem, such as the polynomial Gowers inverse theorem, the classification of approximate Freiman homomorphisms, and quadratic structure-vs-randomness decompositions. Our algorithmic framework is based on a new and optimal version of the Quadratic Goldreich-Levin algorithm, which we obtain using ideas from quantum learning theory. This framework fundamentally relies on a connection between quadratic Fourier analysis and symplectic geometry, first speculated by Green and Tao (Proc. of Edinb. Math. Soc., 2008) and which we make explicit in this paper.