{"ID":23586787,"CreatedAt":"2026-09-18T05:25:32.833479871Z","UpdatedAt":"2026-09-18T05:25:32.833479871Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.20771","arxiv_id":"2609.20771","title":"Marton's conjecture in polynomial time","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 $\\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 stabilizer states, and tomography of quantum states with bounded stabilizer extent.","short_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...","url_abs":"https://arxiv.org/abs/2609.20771","url_pdf":"https://arxiv.org/pdf/2609.20771v1","authors":"[\"Srinivasan Arunachalam\",\"Arkopal Dutt\",\"Sabee Grewal\",\"Aparna Gupte\"]","published":"2026-09-17T17:46:43Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"math.CO\",\"quant-ph\"]","methods":"[]","has_code":false}