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
| CREATOR | Davi Castro-Silva, Jop Briët, Srinivasan Arunachalam, Arkopal Dutt, Tom Gur |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 216246 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.04547