OpenAI’s Astra, their “next major model”, made progress on 10 open problems in math/TCS at a total of “roughly $2,000 at Sol API rates”. See also the 62-page stylised narration of the CoTs (not full CoTs). Jotting it down here for my own reference as part of the ongoing industrialisation of pure math research.
[These problems] have been open and have seen no progress on the main result for at least a decade, and in most cases much longer… All of these problems are of substantial interest to their respective mathematical communities, and several are of broad interest across mathematics as a whole. …
We provide new results for the following problems. …
High-dimensional sphere packing. New upper bounds on sphere-packing density down to the Cohn–Elkies threshold.
Binary and spherical codes: Exponentially improved bounds on the maximum size of binary codes at any prescribed minimum distance, with analogous results for high-dimensional spherical codes.
Non-sofic groups. A construction establishing the existence of non-sofic groups, addressing a central open question in group theory.
Connes’s rigidity conjecture. Disproof of a longstanding conjecture that certain groups are uniquely determined by their von Neumann algebras
Arithmetic circuit complexity. New lower bounds for computing the permanent using arithmetic circuits and formulas, including an arithmetic-formula lower bound of order n4/log n.
Quantum parallel repetition. An exponential parallel repetition theorem for general two-player quantum games, extending a foundational principle from classical complexity theory.
Closest vector problem. Polynomial-factor hardness of approximation for the closest vector problem, a foundational lattice question related to post-quantum cryptography.
Ehrhart’s volume conjecture. Determining, in every dimension, the maximum possible volume of a convex body whose centroid is its only interior lattice point
Multicolor Ramsey numbers. A superexponential lower bound for multicolor triangle Ramsey numbers, resolving Erdős problem 183.
Extremal number conjectures. Results on the compactness and degeneracy conjectures in extremal graph theory, resolving Erdős problems 146 and 180.
The one the sounds most surprising to have been solved to me (disclaimer: I don’t understand a lot of these) is the arithmetic circuit complexity of the permanent. Scott Aaronson suggested trying to analyze the circuit complexity of the permanent (in particular, finding the exact complexity for a small case like ) a while back:
More concretely, my proposal is to devote some of the world’s computing power to an all-out attempt to answer questions like the following: does computing the permanent of a 4-by-4 matrix require more arithmetic operations than computing its determinant?
I wonder if this result provides any more information about that? On the determinant side of things, there was some surprisingly recent progress here: https://arxiv.org/pdf/2301.06586
Ooh nice callout, I do remember that post of Scott’s. Unfortunately I too don’t understand enough to comment. I’ll just quote Scott to motivate the quote you highlighted:
lylebot: Yes, even pure mathematicians often resort to experiment (more often than they admit!) when they want to guess at the truth or falsity of a conjecture. But complexity theory is a special branch of mathematics — one that asks about the asymptotic behavior, not of some particular algorithm or a typical algorithm, but of the best algorithm that could possibly exist. And the set of possible algorithms is both huge beyond imagination and lacking in any simple characterization. That’s why, in the past, experimental work has not been a big help to complexity theory: because the amount of computation that you’d have to do to learn anything interesting is so astronomical. My “wild & crazy” proposal is that we at least ask ourselves whether that’s still true, given both the better understanding and the vastly increased computing power that we have today.
Do we know whether the $2k figure is the tokens cost of the entire project, including any runs with a null result? Or is it the cost of the subset of the work that produced these 10 results?
The article didn’t specify. I’d be comfortable betting on the latter, since $200 per solution is in the ballpark of e.g. what the recent GDM agent did. I’d guess 10-100x more for the former.
OpenAI’s Astra, their “next major model”, made progress on 10 open problems in math/TCS at a total of “roughly $2,000 at Sol API rates”. See also the 62-page stylised narration of the CoTs (not full CoTs). Jotting it down here for my own reference as part of the ongoing industrialisation of pure math research.
The one the sounds most surprising to have been solved to me (disclaimer: I don’t understand a lot of these) is the arithmetic circuit complexity of the permanent. Scott Aaronson suggested trying to analyze the circuit complexity of the permanent (in particular, finding the exact complexity for a small case like
I wonder if this result provides any more information about that? On the determinant side of things, there was some surprisingly recent progress here: https://arxiv.org/pdf/2301.06586
Ooh nice callout, I do remember that post of Scott’s. Unfortunately I too don’t understand enough to comment. I’ll just quote Scott to motivate the quote you highlighted:
Do we know whether the $2k figure is the tokens cost of the entire project, including any runs with a null result? Or is it the cost of the subset of the work that produced these 10 results?
The article didn’t specify. I’d be comfortable betting on the latter, since $200 per solution is in the ballpark of e.g. what the recent GDM agent did. I’d guess 10-100x more for the former.