Polynomial algorithm finds structured covers for complex sets in vector spaces
Marton's conjecture in polynomial time
Computational Complexity
Summary
Some sets of points can be complicated, but mathematicians found a way to describe them using simpler building blocks called subspaces. The authors created a fast algorithm that, when given certain access to such a set, finds a small number of these building blocks that together cover the set. This helps solve problems in areas like learning certain patterns and understanding special quantum states. Their work turns a recent theoretical discovery into a practical tool.
What this means in practice
- •For machine learning engineers: Compute subspaces efficiently from data with low doubling to improve learning of complex patterns.
- •For quantum computing developers: Perform tomography on certain quantum states using algorithms enabled by the polynomial-time subspace cover.
Authors
Srinivasan Arunachalam, Arkopal Dutt, Sabee Grewal, Aparna Gupte
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.