Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated just now
PreprintarXiv licencearXiv

Marton's conjecture in polynomial time

  • Srinivasan Arunachalam
  • Arkopal Dutt
  • Sabee Grewal
  • Aparna Gupte
Open at sourcePDFDOICite

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 ⊆ 𝔽2n with doubling constant at most K, our algorithm outputs a subspace of size at most |A| whose KO(1) translates cover A. The algorithm runs in textsfpoly(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.

Related

  1. An Improvement to the Upper Bound for Marton's Covering Conjecture
    Zhao Song, Song Yue
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. On the dynamical Manin–Mumford conjecture for plane polynomial maps
    Romain Dujardin, Charles Favre, Matteo Ruggiero
    Journal of the European Mathematical SocietyPeer-reviewedCC BY10 citedGeometry & topologyHALOpenAlex
  3. Polynomial Counterexamples to Shanks' Conjecture in Dirichlet-Type Spaces over the Bidisc
    Oliver Navío, Daniel Seco
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  4. Nagata's conjecture on a polynomial automorphism in positive characteristic
    Shigeru Kuroda
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  5. The weak cylinder conjecture for polynomial graphs of bounded degree
    Daniele Bartoli, Alessandro Giannoni
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{arunachalam2026martons,
  title = {{Marton's conjecture in polynomial time}},
  author = {Srinivasan Arunachalam and Arkopal Dutt and Sabee Grewal and Aparna Gupte},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.20771},
  eprint = {2609.20771},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.20771},
}
RIS
TY  - UNPB
TI  - Marton's conjecture in polynomial time
AU  - Srinivasan Arunachalam
AU  - Arkopal Dutt
AU  - Sabee Grewal
AU  - Aparna Gupte
PY  - 2026
DA  - 2026/09/17
PB  - arXiv
DO  - 10.48550/arxiv.2609.20771
UR  - https://arxiv.org/abs/2609.20771
AB  - 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 ⊆ 𝔽_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 textsfpoly(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.
ER  -