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 received his PhD from the Management Science and Engineering department at Stanford University in 2013. After a postdoctoral fellowship at Berkeley he joined University of Washington, where he is an associate professor. In the decade since his PhD, 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, Kiukiu Liu and Cynthia Vinzant, Oveis Gharan developed fundamentally new techniques. The new results also settled several decades-old open problems, such as the Mihail-Vazirani conjecture on efficient sampling of bases of a matroid and the Mason conjecture in algebraic combinatorics.

One could mention an number of other research highlights. Let me just give as a third example his fundamental work in spectral graph theory on higher-order Cheeger inequalities with Lee and Trevisan.

The new techniques by which he arrived at these spectacular new results in each case 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.