What does an improved upper bound on ω mean
In August 2026, we uploaded a note on arXiv, proving ω < 2.371177. This post explains what this means and why we care.
Given a large graph, say we want to count the number of triangles, i.e., the number of triples of nodes that are all connected to each other. A natural way is to loop over all triples of nodes and check whether they form a triangle:
def count_triangles(graph):
num_triangles = 0
for (i,j,k) in itertools.combinations(graph.nodes,3):
if i, j, k are all connected to each other, then num_triangles += 1
return num_triangles
If your graph has n nodes, the time complexity of this is n choose 3, which is O(n³). But we can do better.
They key idea is to represent the graph as an n by n binary matrix A, called the adjacency matrix: for each pair i, j of nodes, you put a 1 at entry [i, j] if nodes i and j are connected, and 0 otherwise. Then, it’s not hard to see that the number of triangles in the graph equals Tr (A³) / 6, where Tr (A³), called the trace of A³, is the sum of diagonal entries of the matrix A³. So, since calculating the trace of a matrix is O(n), if we could somehow construct the matrix A³ faster than O(n³), we could count the number of triangles faster. But how to construct the matrix A³ ?
First, you need to construct A². The natural way is to do a for loop over all rows and columns of A and compute their dot product:
def square_matrix(A):
n = A.shape[0]
return np.array([[np.dot(A[i, :], A[:, j]) for j in range(n)] for i in range(n)])
But this also takes time O(n³), as calculating each dot product takes time O(n). So, it seems like switching to the matrix notation hasn’t helped at all, but then there is a surprise.
Strassen’s algorithm and further improvements
In 1969, Volker Strassen came up with a surprising algorithm to multiply any two n by n matrices A and B within time O(n^2.8074). The algorithm is simple to describe (see Wikipedia), and the main idea is to find an elegant way of factoring the product matrix AB so you can reuse some calculations. To illustrate why this can even be possible with a supersimple example, suppose instead that you wanted to calculate the quantity a² + 2ab + b² for two numbers a and b. The naive approach is computing each of a², 2ab, b², and then adding them up, which requires 4 multiplications and 2 additions. Alternatively, if you use the identity
a² + 2ab + b² = (a+b)²,
you can instead calculate a+b and then multiply it with itself. This requires 1 addition and 1 multiplication. So, by rewriting a mathematical expression in a different way, you may be able to compute it faster, although both expressions are mathematically equivalent.
Get Abbas Mehrabian’s stories in your inbox
Join Medium for free to get updates from this writer.
After Strassen published his clever algorithm to multiply two square matrices in time O(n^2.8074), a natural question appeared: can you reduce the exponent further? Well, after 9 years Victor Pan answered yes, publishing an algorithm with complexity O(n^2.796). Then a series of mathematical papers followed, building idea on top of idea, reaching the state-of-the-art algorithm, as of July 2026, with time complexity O(n^2.371339).
This table (copied from Wikipedia) shows the sequence of improvements, and as you can see, they have been really tiny since 1990 (in this table, ω is defined as the smallest constant such that you can multiply two n by n matrices in time O(n^ω)). Still, each improvement required a genuinely new mathematical idea.
Our contribution
And then, in August 2026, we improved the upper bound on ω by a tiny bit more, to 2.371177. Let me give some background on how we did it.
The mathematical theory developed to prove this sequence of bounds is quite rich and touches different fields of mathematics. Although the problem originated from computational complexity, which is a subfield of theoretical computer science, Strassen reformulated it as a problem in algebraic geometry (showing a fascinating relationship between a computational concept and a geometric concept), and all subsequent work took this approach, bringing in ideas from areas such as analysis, combinatorics, and probability theory. And all papers after 1986 further reformulated the problem as a numerical optimization problem and showed that any feasible solution to this problem yields an upper bound on ω.
The 2024 paper of Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou recorded the best upper bound before our work. They formulated a massive nonconvex optimization problem with 25 thousand variables, solved it using MATLAB (it took them weeks to solve it!) and showed ω < 2.371339. They also mentioned that there is an even larger version of their optimization problem, with 7 million variables, which potentially gives a better bound, but added that solving this larger problem “seems infeasible, at least with the current solver.”
And that’s when we arrived. Joining forces with some of the authors of that paper, we smoothed out their optimization problem, used the gradient-based Adam optimization algorithm, better parallelization, JAX, and GPUs, which allowed us to solve their larger optimization problem and prove ω < 2.371241.
Then we improved this further by using AlphaEvolve, a coding agent our team has developed that uses large language models to solve large numerical optimization problems (it has many more applications in other areas as well, see this blog post for examples). Here is an oversimplification of the general idea: we provide Gemini with a feasible solution to the huge optimization problem as well as the code for the Adam optimization algorithm, and ask Gemini to improve the algorithm and obtain a better feasible solution. Once Gemini comes up with a better code and a better solution, we repeat this process in an evolutionary framework, until Gemini is stuck and can’t improve the solution any further. At this point, we have found a solution that yields ω < 2.371177.
We hope this result further shows the potential of AlphaEvolve and motivates more people to approach their numerical optimization problems using large language models.
Final remarks
For me, finding the precise value of ω is a mathematical pursuit. Matrix multiplication is a fundamental operation in the theory of computation, and ω is a fundamental constant in the theory of computation. (Scott Aaronson likens it to the mass of the Higgs boson, a fundamental quantity in physics that is known to be between 125 and 125.22 GeV.) Today, we know that 2 ≤ ω < 2.371177 and surprisingly, no lower bound other than 2 is known. In fact, many people believe that ω = 2, which would be quite a surprise if it’s true. I personally don’t think the precise value of ω will be determined in the next 50 years (but the large language models are advancing mathematics at an unbelievable speed, and I may be proven wrong very soon).
I motivated this post via the problem of counting the number of triangles in a graph, but the complexity of matrix multiplication determines the complexity of many more problems in theoretical computer science, including solving linear programs, computing determinants, parsing context-free grammars, and finding all-pairs shortest paths in graphs. Moreover, matrix multiplication is ubiquitous in computers but as far as I know, the classic O(n³) algorithm is still used in today’s chips to multiply matrices. This could have many reasons: most algorithms shown in the table above are difficult to implement, they are asymptotic algorithms and are faster for very large matrices but slow for small matrices that arise in practice, or they may be numerically unstable or hard to parallelize. To learn more about practical aspects of matrix multiplications, please see this 2025 talk.
For a more complete history of ω and approaches to bound it, see this 2025 talk by our coauthor Virginia Vassilevska Williams, and if you really want to learn the technical details, see this 2013 survey paper.
PS. Yesterday, OpenAI published a paper proving ω ≤ 2.25, a major breakthrough since 1990. The proof is very innovative and develops a completely new technique for bounding ω.
