An algorithmic Polynomial Freiman-Ruzsa theorem
This work addresses foundational problems in additive combinatorics and theoretical computer science by making structural results algorithmic, which is significant for researchers in these fields.
The paper tackles the problem of providing algorithmic versions of the Polynomial Freiman-Ruzsa theorem, resulting in a polynomial-time algorithm that, for a set with doubling constant K, returns a subspace of size at most |A| such that A can be covered by 2K^C translates, with C being a universal constant.
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 \subseteq \mathbb{F}_2^n$ with doubling constant $K$, returns a subspace $V \subseteq \mathbb{F}_2^n$ of size $|V| \leq |A|$ such that $A$ can be covered by $2K^C$ 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.