Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ARKOPAL DUTT:
All reports by Author Arkopal Dutt:

TR25-130 | 2nd September 2025
Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, Tom Gur

Algorithmic Polynomial Freiman-Ruzsa Theorems

We prove algorithmic versions of the polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) in additive combinatorics. In particular, we give classical and quantum polynomial-time algorithms that, for $A \subseteq \mathbb{F}_2^n$ with doubling constant $K$, learn an explicit description of a subspace $V \subseteq \mathbb{F}_2^n$ ... more >>>




ISSN 1433-8092 | Imprint