Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-189 | 17th September 2026 20:35

Marton's conjecture in polynomial time

RSS-Feed




TR26-189
Authors: Srinivasan Arunachalam, Arkopal Dutt, Sabee Grewal, Aparna Gupte
Publication: 17th September 2026 20:47
Downloads: 152
Keywords: 


Abstract:

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 $K^{O(1)}$ translates cover $A$. The algorithm runs in $\mathrm{poly}(n,K)$ time. As applications, we obtain polynomial-time algorithms for a variety of learning problems, including quadratic Goldreich–Levin, improper agnostic tomography of stabilizer states, and tomography of quantum states with bounded stabilizer extent.



ISSN 1433-8092 | Imprint