{"id":"arxiv/2604.04547","url":"https://arxiv.org/abs/2604.04547","tags":["math.CO","cs.DS"],"score":0,"title":"An algorithmic Polynomial Freiman-Ruzsa theorem","domain":"math.CO","source":"arxiv","authors":["Davi Castro-Silva","Jop Briët","Srinivasan Arunachalam","Arkopal Dutt","Tom Gur"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-06","reactions":{}}