quantum complexity

Noam Brown @polynoamial

2026-08-01 — saved image

Noam Brown @polynoamial · 10h
An internal version of Astra, @OpenAI's next major model family, solved 10 major open problems in mathematics, quantum complexity, and theoretical computer science.

We believe it will be a major step for scientific reasoning. openai.com/index/ten-adva...

[embedded image, numbered list]
1. High-dimensional sphere packing. The asymptotic strength of the Cohn–Elkies linear program is determined exactly. This gives an improved general packing bound in high dimensions and settles the corresponding Fourier sign-uncertainty problem asymptotically.
2. Binary and spherical codes. Classical upper bounds for fixed-distance binary and spherical codes are improved by exponential factors for all parameters. The spherical construction also recovers the sphere-packing exponent of Chapter 1.
3. Non-sofic groups. An explicit non-sofic group is constructed, resolving the question of whether every countable group admits finite permutation approximations. The argument uses property-(T) expanders and the binary Leavitt algebra.
4. Connes's rigidity conjecture. Infinitely many pairwise nonisomorphic property-(T) groups are constructed with the same group von Neumann algebra, disproving Connes's conjecture and answering a related finite-to-one question.
5. Arithmetic circuit complexity. For the permanent, division-free circuits require Ω(n²log log n) gates, while formulas require Ω(n⁴/log n) leaves.
6. Quantum parallel repetition. Exponential parallel repetition is proved for every finite two-player entangled game, extending the classical repetition principle beyond previously treated special classes of quantum games.
7. Closest vector problem. A direct reduction from 3SAT gives n^(1/400)-factor hardness for Euclidean closest vector, with related consequences for binary decoding and other lattice norms.
8. Ehrhart's volume conjecture. The sharp bound (n+1)^n/n! is proved in every dimension for convex bodies whose barycenter is their only interior lattice point.
9. Multicolor Ramsey numbers. A superexponential lower bound proves R_k(3) = k^Θ(k).
10. Compactness and degeneracy. Separate bipartite graph constructions disprove two conjectures in extremal graph theory: the compactness conjecture of Erdős and Simonovits and a degeneracy conjecture of Erdős.

Lijie Chen @wjmzbmr1 · 10h
10 proofs from our next major model Astra on long-standing open problems in mathematics and theoretical computer science (also including new circuit lower bounds for computing the permanent!)...

openaiastramathematicsai researchtheoretical computer sciencequantum complexity