{"id":"arxiv/2609.20771","url":"https://arxiv.org/abs/2609.20771","tags":["cs.CC","math.CO","quant-ph"],"score":0,"title":"Marton's conjecture in polynomial time","domain":"cs.CC","source":"arxiv","authors":["Srinivasan Arunachalam","Arkopal Dutt","Sabee Grewal","Aparna Gupte"],"reviews":0,"subject":"cs.CC","summary":"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 $\\textsf{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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-17","reactions":{}}