Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIAL FREIMAN-RUZSA:
Reports tagged with Polynomial Freiman-Ruzsa:
TR26-189 | 17th September 2026
Srinivasan Arunachalam, Arkopal Dutt, Sabee Grewal, Aparna Gupte

Marton's conjecture in polynomial time

Gowers, Green, Manners, and Tao (Annals '25) recently resolved Marton's polynomial Freiman–Ruzsa conjecture. We give an algorithmic counterpart to their result: given uniform sampling and membership-oracle access to a set $A \subseteq \mathbb{F}_2^n$ with doubling constant at most $K$, our algorithm outputs a subspace of size at most $|A|$ whose ... more >>>




ISSN 1433-8092 | Imprint