Shayan Oveis Gharan has made it his mission to tackle some of the most famous — and famously hard — problems underpinning computer science. A member of the Theory of Computation Group and Edward D. Lazowska Professor in Computer Science & Engineering at the University of Washington, Oveis Gharan has contributed to an impressive series of results that have moved the field forward, from offering the first improvement to the Traveling Salesperson Problem (TSP) in more than four decades, to proving a 30-year old conjecture about counting the bases of matroids.
The International Mathematical Union recently honored Oveis Gharan with the 2026 IMU Abacus Medal for “landmark contributions to the theory of algorithms.” The IMU awards the Abacus Medal every four years to a researcher under the age of 40 who has made outstanding contributions in the mathematical aspects of the information sciences. Announced at the same time as the Fields Medal, both recognize generational talent and are among the most prestigious prizes in mathematics.
Although the awards are a closely guarded secret leading up to the public announcement, Oveis Gharan had a hunch even before the official notice came.
“I first received an email from the president of IMU for a Zoom call back in September, and I immediately guessed it must be for this award. Because you normally would not get an email from the president of IMU,” he said with a laugh. “I am very happy for my colleagues and collaborators and everyone in my areas of research — approximation algorithms, analysis of Markov chains, and spectral graph theory — to be recognized and hopefully get better support in the future for their brilliant contributions to the field.”
According to Oveis Gharan, those areas of research hit the sweet spot between the beauty of “pure” mathematical theory and the real-world applicability of computing.
“Pure mathematics is so beautiful because we can prove theorems about truths in the world that hold independent of time and location. They may be used tomorrow, or thousands of years from now, or never, but when you have a correct proof, nobody can downgrade it,” Oveis Gharan explained. “Theory of computing stands out for me because it’s a branch of mathematics that tries to prove statements that, in my opinion, are significantly more related to the real world.
“In a sense, my work combines the best of both worlds,” he continued. “On one hand, I look for the truth about mathematical objects such as spanning trees, matroids, matchings, et cetera, and on the other hand, I design algorithms which may be used to solve basic daily-life tasks.”
A prime example — and one of Oveis Gharan’s career-defining accomplishments to date — has been his work on TSP, which aims to find the shortest route between a network of cities and back to the start while visiting each location only once. It is one of the most recognized and intensely studied problems in combinatorial optimization. When Oveis Gharan was a doctoral student at Stanford University, Christofides’ famous 3/2 algorithm, published back in 1976, could approximate a solution that was, at most, “only” 50% longer than the ideal round trip. He began chipping away at the problem, applying concepts such as randomness, maximum entropy sampling, negative dependence, the geometry of polynomials and other tools to achieve the first improvement over Christofides’ 3/2-approximation for the symmetric graph case and the first asymptotic improvement on the asymmetric TSP.
My work combines the best of both worlds. On one hand, I look for the truth about mathematical objects such as spanning trees, matroids, matchings, et cetera, and on the other hand, I design algorithms which may be used to solve basic daily-life tasks.
According to faculty colleague and fellow traveler Anna Karlin, Oveis Gharan’s persistence is fundamental to his success — along with his sparkling personality. “He’s incredibly fun to work with,” she told Quanta Magazine. “He’s a believer that you can make progress.”
That belief was vindicated when Oveis Gharan eventually teamed up with Karlin and Allen School doctoral student Nathan Klein (Ph.D., ‘23) to, at long last, obtain a provably better approximation factor than Christofides’ 3/2-approximation on any metric.
“The main outcome of our work is not only a slightly improved approximation, but that 50% is not the limit of what you can do with computers efficiently. You should be able to do much better,” he explained in a Simons Foundation video. “And now many researchers are trying to use our ideas to design a much better approximation for TSP.”
Oveis Gharan has a knack for coming up with ideas and tools that other researchers can run with. For instance, he worked with Allen School doctoral student Kuikui Liu (Ph.D., ‘23), UW Department of Mathematics professor Cynthia Vinzant and Stanford University professor Nima Anari on a novel technique for approximate sampling of Markov chains called spectral independence, which they used to develop the first fully polynomial randomized approximation scheme (FPRAS) algorithm for efficiently counting the bases of matroids. In the process, they also proved a 30-year old conjecture concerning the minimum edge expansion of the bases exchange graph of any matroid.
But they didn’t stop there. Oveis Gharan, Liu and Anari then applied the technique to resolve an open problem in statistical physics related to sampling from the hardcore model, proving for the first time that Glauber dynamics — an algorithmic tool for modeling ferromagnetism — mixes in polynomial time up to the so-called phase-transition threshold. Shortly after publishing this result, Oveis Gharan was delighted to see researchers finding even more uses for spectral independence in a variety of domains. It’s why, when asked to identify his favorite result from his career so far, he’s inclined to point to this, rather than TSP, as his answer.
“Over a short period of time, this new technique revolutionized the field of approximate counting and sampling,” he recalled. “Every few weeks, I would see a new paper either generalizing our results or finding new applications in some distant area of research.”
Until now, Oveis Gharan’s work has mostly dealt with what he calls the “positive directions” in theoretical computer science, showing that certain tasks are possible with efficient algorithms. But he’s curious to explore the flip side to demonstrate that certain tasks are impossible with these algorithms. He points out that, already, the existence of “fast” algorithms for some tasks can prove the impossibility of using them for other tasks.
“Surprisingly, these two areas aren’t actually that far from one another. One of my favorite questions in this regard has to do with the theory of pseudorandomness. That is, how can we turn randomized algorithms to (possibly slightly slower) deterministic algorithms?” Oveis Gharan said. “Besides having enormous practical importance, such results would have a significant impact on the area of complexity theory. One problem in this area that I’d like to work on is how to turn randomized algorithms that use only logarithmic space to deterministic algorithms (with logarithmic space).”
Whether he’s setting out to prove what’s possible or impossible, Oveis Gharan says he loves his chosen area because, unlike other areas of computing, the results tend to endure — even as other aspects of the field may fade with time.
“In most areas of computer science, you see algorithms developed 20 years ago or so are now obsolete, perhaps because of the advances in AI,” he observed. “But that’s not the case with CS theory.”
The IMU Abacus Medal is funded jointly by the University of Helsinki and the Simons Foundation. It is the latest in a series of honors Oveis Gharan has earned for his body of work, which includes the Stephen Smale Prize from the Society for the Foundations of Computational Mathematics (FoCM), the Michael and Sheila Held Prize from the National Academy of Sciences, a Simons Investigator Award from the Simons Foundation and the EATCS Presburger Award for Young Scientists from the European Association for Theoretical Computer Science.
Learn more about Oveis Gharan’s contributions on the IMU website, read his medal profile in Quanta Magazine, and watch the Simons Foundation video about his life and work.