Professor Shayan Oveis Gharan, a member of the Allen School’s Theory of Computation group, was named a 2022 Simons Investigator by the Simons Foundation for his innovative approach to fundamental problems in algorithm design and combinatorial optimization. The Simons Investigator Award is designed to support outstanding theoretical scientists in mathematics, physics, astrophysics and computer science as they pursue creative new research directions, mentor junior scientists, and provide leadership within their respective fields.
Oveis Gharan is perhaps best known in theoretical computer science circles for his devotion to the Traveling Salesperson Problem — a devotion that has propelled him to achieve state-of-the-art results on a core research question in combinatorial optimization with practical applications in many other domains. His impact stretches back to his time as a Ph.D. student, when he worked with his advisor, Stanford University professor Amin Saberi, and McGill University professor Mohit Singh to produce the first improved approximation algorithm for the special case of metric TSP called graphic TSP in 35 years. Their simple yet powerful algorithm, which drew upon ideas from probability theory, graph theory and polyhedral theory, earned the Best Paper Award at the 52nd annual IEEE Symposium on Foundations of Computing (FOCS 2011).
After his arrival at the University of Washington in 2015, Oveis Gharan continued to make progress on his favorite problem. After a decade of effort that began during his Ph.D., he and Allen School colleague Anna Karlin and Ph.D. student Nathan Klein managed to extend the 2011 result and design the first improvement over the Christofides algorithm for any metric in more than 40 years. In addition to the temporal significance, the result was hugely symbolic: Oveis Gharan and his co-authors had devised the first algorithm capable of producing a solution that costs less than 50% above the optimum. The team’s achievement earned the Best Paper Award at the 53rd annual Symposium on Theory of Computing (STOC 2021).
Despite the seriousness of the subject — after all, the TSP is one of the problems underpinning the field — it’s evident that Oveis Gharan genuinely enjoys the challenge. And his collaborators enjoy it right along with him.
“Shayan is technically brilliant and intellectually fearless. He tackles only the hardest and most fundamental problems. These are problems that have remained open for decades, despite the attention of numerous researchers. And time and again, to my and other colleagues’ amazement, he makes progress on those problems,” said Karlin. “I cannot resist adding that he is also the most enthusiastic, generous and fun collaborator one could imagine working with.”
Oveis Gharan’s progress on fundamental — and fundamentally hard — problems extends beyond TSP. One of his recent results that has spurred a flurry of follow-on work within the theoretical computer science community resolved a two-decades-old open problem concerning the sampling of independent sets of a graph up to the computational complexity threshold. In the paper “Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model,” Oveis Gharan and his co-authors, Allen School Ph.D. student Kuikui Liu and Stanford University professor Nima Anari, showed for the first time that Glauber dynamics — an algorithmic tool used in statistical physics for modeling ferromagnetism — mixes in polynomial time for any graph, not just a subset of graphs, up to the phase-transition threshold, after which the problems become computationally intractable. After much follow-on work, another team subsequently built on their result to finally show that one can sample an independent set of a graph, up to the phase-transition threshold, in near-linear time — essentially, in the same time as sorting the vertices of the graph. Although the work is not yet two years old, having first appeared at FOCS 2020, it has already inspired more than 50 follow-on papers and was subsequently featured in the SIAM Journal of Computing published by the Society for Industrial and Applied Mathematics.
The above result built on previous work by the team in conjunction with UW Mathematics professor Cynthia Vinzant — at the time, a faculty member at North Carolina State University — that linked the analysis of Markov chains and the field of high dimensional expanders. In one of a series of papers to advance the theory of completely log-concave polynomials to study the combinatorial structure of matroids, they presented the first fully polynomial randomized approximation scheme (FPRAS) for counting the bases of a matroid. This novel approach, which is based on a simple two-step Markov Chain Monte Carlo process, enables the sampling of random spanning forests in a graph to estimate the reliability polynomial of any matroid. In the same paper, Oveis Gharan and his co-authors also proved the 30-year-old Mihail-Vazirani conjecture that the bases exchange graph of any matroid has edge expansion of at least 1. The team earned a Best Paper Award at STOC 2019 for their contributions, which have real-world applications for network reliability, data transmission, and more.
“Shayan is at the forefront of a series of exciting discoveries that are advancing our understanding of the foundations of computing. The impact he’s already made, so early in his career, is astonishing,” said Allen School colleague James R. Lee, who was named a Simons Investigator in 2017. “His application of algebraic and spectral methods to algorithm design and combinatorial optimization is expanding the mathematical and algorithmic toolbox for our entire community. And along the way, he’s making progress on some of the most significant and longest-standing problems in the field.”
Oveis Gharan’s designation as a Simons Investigator is the latest in a string of accolades that he has accumulated since his arrival at the Allen School, including the EATCS Presburger Award from the European Association for Theoretical Computer Science in 2021 and a Sloan Research Fellowship in 2019.
Learn more about the 2022 Simons Investigators here.
Congratulations, Shayan!