About the prize winner

Shayan Oveis Gharan

The fifth Stephen Smale prize is awarded to Shayan Oveis Gharan, University of Washington, for his breakthrough results on the applications of algebraic and spectral methods to the design of algorithms and to combinatorial optimization.

He has been the architect of surprising and profound discoveries on foundational problems in computing. These concern, for example, the Traveling Salesman Problem, graph partitioning, the combinatorial structure of matroids, and the analysis of Markov chains. With his students and coauthors, he has achieved breakthroughs on several long-standing problems.

His first major line of research addresses the metric and the asymmetric Traveling Salesman problem. For the metric version of the problem, using modern tools from probability theory, spectral graph theory and geometry of polynomials, in a sequence of papers with Anna Karlin and Nathan Klein he managed to obtain the first deterministic approximation algorithm that improves on the 3/2 barrier on the approximation factor after four decades. In a different line of work, Oveis Gharan with Nima Anari designed the first polyloglog(n)-algorithm for the asymmetric Traveling Salesman problem, another improvement on a classical result after several decades.

A second major line of research concerns the convergence of Markov Chain Monte Carlo algorithms. In collaboration with Nima Anari, Kuikui Liu and Cynthia Vinzant, Oveis Gharan developed fundamentally new techniques for bounding convergence rates of Markov chains, known as the spectral independence method. The new results also settled several decades-old open problems, such as the Mihail-Vazirani conjecture on random walks on matroids and the strongest form of the Mason conjecture on independent sets of matroids.

The new techniques by which he arrived at his spectacular results span several mathematical fields and have been influential in shaping the research landscape. His beautiful and groundbreaking results connect pure mathematics and computational algorithms, and are thus very much in the spirit of the Smale prize.

The prize was awarded on June 13, 2023, at FoCM'23 in Paris. The winner received a "Gömböc" as the prize insignia.

Smale Prize 2023 committee