An algorithmic Polynomial Freiman–Ruzsa theorem

Davi Castro-Silva, Jop Briët, Srinivasan Arunachalam, Arkopal Dutt, Tom Gur · 2026

Read An algorithmic Polynomial Freiman–Ruzsa theorem by Davi Castro-Silva, Jop Briët, Srinivasan Arunachalam, Arkopal Dutt, Tom Gur (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-04547.txt.

Description

Castro-Silva and four colleagues give versions of the Polynomial Freiman-Ruzsa theorem. They give a fast algorithm that, given a set A in F2 to the n with doubling K, returns a subspace V no larger than A. A is covered by 2K to the C translates. They also give fast algorithms for matching forms. Their framework rests on a new and optimal Quadratic Goldreich-Levin algorithm from quantum learning. It relies on a link between quadratic Fourier analysis and symplectic geometry, guessed by Green and Tao.

Catalog record

CREATORDavi Castro-Silva, Jop Briët, Srinivasan Arunachalam, Arkopal Dutt, Tom Gur
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE216246
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.04547

Browse the full library · About the Tower of Babel