Skip to content
Preprint

Marton's conjecture in polynomial time

Sep 2026 · 3 citations · ⚡ 1 influential
Computer Science Mathematics Physics

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.

View source

Similar papers

Sep 2026

Vector Balancing in Polynomial Time

The Koml\'os problem asks for signs $\varepsilon\in\{-1,1\}^n$ with $\|A\varepsilon\|_\infty$ bounded by an absolute constant whenever the columns of $A\in\mathbb R^{m\times n}$ have Euclidean norm at most $1$. We give the first polynomial-time algorithm for this problem in the unit-cost real-RAM model. Our determinist...

Sheng Guo, Ethan X. Fang, Jun-Wei Lu · 4 citations · ⚡2
Preprint Aug 2026

A Counterexample to Belinsky's Conjecture on Ces\`aro Means at Lebesgue Points

In 1997, Belinsky conjectured that, for convex subsequences, the logarithmic growth condition of Carleson, Trigub, and Zagorodni\u{\i} is necessary and sufficient for the arithmetic means of subsequential Fourier partial sums to converge at every Lebesgue point of every integrable function. We disprove the sufficiency...

U. Goginava · 0 citations
Preprint Sep 2026

A near-linear upper bound for Burr's conjecture

Let $f(k)$ denote the smallest integer such that every oriented graph $D$ with chromatic number at least $f(k)$ contains every oriented tree on $k$ vertices. Burr (1980) showed that $f(k)\le (k-1)^2$ and conjectured that $f(k)=2k-2$. Bessy, Gon\c{c}alves and Reinald (2025) proved that $f(k)=O(k^{3/2})$. In this paper,...

Liang-Dong Fan, Jun-Ying Lu, Yao-Jun Chen · 0 citations
Preprint Sep 2026

A somewhat sure note on an un-Schur problem

Parczyk and Spiegel initiated the study of an anti-Ramsey multiplicity variant of Schur's theorem and proved that the maximum fraction of Schur triples that can be rainbow in a $3$-coloring of $\{ 1, \dots ,n \}$ is bounded asymptotically between $0.4$ and $0.66364$. Furthermore, they conjectured that their lower bound...

Swaroop G. Hegde, Hitesh Kumar, Pratibha · 0 citations
Preprint Sep 2026

Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE

A deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest, and a full sample--time tradeoff that interpolates between exponential and polynomial runtime is established.

Robin Kothari, Tony Metger, Ryan O'Donnell et al. · 0 citations
Preprint Aug 2026

A new lower bound for two-color van der Waerden numbers

The van der Waerden number $w(k)$ is the smallest positive integer $N$ such that every two-coloring of $\{1,2,\ldots,N\}$ contains a monochromatic $k$-term arithmetic progression. We prove that $w(k) \geq (1-o(1))k2^{k-1}$ holds for all positive integers $k$. This verifies a conjecture of Erd\H{o}s. In 1968, Berlekamp...

Marcelo Campos, Jacob Fox, C. Schildkraut · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.