Professor Shayan Oveis Gharan, a member of the Allen School’s Theory of Computation group, earned the 2021 Presburger Award for Young Scientists from the European Association for Theoretical Computer Science (EATCS) for his research on the Traveling Salesperson Problem (TSP). Each year, the EATCS bestows the Presburger Award on an early-career scientist who has made outstanding contributions in the field of theoretical computer science. In its unanimous selection of Oveis Gharan for this year’s honor, the award committee heralded his “creative, profound, and ambitious” work on a fundamental problem that has advanced scientists’ understanding of the design and analysis of algorithms.
“Shayan is a leader in the application of algebraic and spectral methods to classical problems in combinatorial optimization, and he’s the architect of a series of surprising and profound developments in the theory of algorithms,” said Allen School professor James Lee. “He exhibits a remarkably consistent ability to make progress on important problems that had remained open for decades.”
That progress began when Oveis Gharan was a Ph.D. student at Stanford University, where he and his collaborators produced an approximation algorithm that offered the first asymptotic improvement on TSP in the asymmetric case in three decades. It has culminated — so far, at least — in the first performance improvement on metric TSP in nearly half a century. In between, Oveis Gharan also contributed to the first improvement over Christofides’ 3/2-approximation for the symmetric graph case of TSP, first put forward in 1976, in what the Presburger Award committee describes as a “remarkable tour de force.” Over the course of his career, Oveis Gharan has continued to develop and expand the concept of “negative dependence” between the presence of edges in a certain distribution on random spanning trees of a graph — a tool he first applied to great effect in his initial contribution to TSP as a student — to push the field forward.
For his latest milestone, Oveis Gharan worked with Allen School Ph.D. student Nathan Klein and faculty colleague Anna Karlin to devise an approximation algorithm capable of returning a solution that surpasses 50% of the optimum for the very first time. The team will receive a Best Paper Award at the Association for Computing Machinery’s upcoming Symposium on the Theory of Computing (STOC 2021) for their groundbreaking achievement. According to Karlin, Oveis Gharan stands out not only for his technical contributions, but also for the way he approaches his research.
“Shayan is an exceptionally brilliant, ambitious and fearless researcher,” said Karlin. “What blows my mind is that, on top of all of that, he is also one of the kindest, most generous people I know. Every meeting with Shayan and our students lifts my spirits because he brings such enthusiasm, warmth and positivity to his work.”
The central question of TSP — how to determine the shortest and most efficient route between multiple destinations and back to the starting point — is more than a theoretical problem. It has multiple real-world applications across a variety of domains, from planning and scheduling, to supply chain logistics, to microchip manufacturing. It also has provided an ideal vehicle for Oveis Gharan to apply his expertise in analysis, probability and combinatorics to push the theoretical limits of computation and enable progress in other fields while providing the inspiration and the tools for other young researchers to follow his lead.
“Shayan’s enthusiasm for what he does is infectious, and he has helped me gain a new appreciation of computer science. He communicates to his students a strong sense that we are not here just to solve problems but to learn, grow, and discover new ideas,” Klein said. “He also has a great ability to zoom out and synthesize. For example, during the TSP project I came to him with a mess of proofs of a dozen probabilistic lemmas we needed. He immediately recognized a common theme and extracted an elegant theorem that characterized all of these lemmas and more. This theorem ended up being quite useful in guiding our understanding for the remainder of the project.”
While the challenge of TSP may hold particular fascination for Oveis Gharan, it is not the only open problem on which he has made notable progress in recent years. In 2019, he earned a STOC Best Paper Award for his work with Allen School Ph.D. student Kuikui Liu and collaborators on the first fully polynomial randomized approximation scheme (FPRAS) for counting the bases of a matroid. Drawing from several seemingly unrelated areas of mathematics and theoretical computer science — namely Hodge theory for combinatorial geometries, analysis of Markov chains, and high dimensional expanders — the team applied a novel theory of spectral negative dependence to prove a conjecture by Mihail and Vazirani that had remained an open question for 30 years. As a follow-up, members of that team applied some of those same insights to sampling an independent set from the hardcore model. Their results addressed a 25-year-old open problem concerning the mixing time of Glauber dynamics by proving that, for any graph, they mix in polynomial time up to the tree uniqueness threshold.
Since his arrival at the University of Washington in 2015, Oveis Gharan has earned a Sloan Research Fellowship, a CAREER Award from the National Science Foundation, an ONR Young Investigator Award from the Office of Naval Research, and a Google Faculty Research Award. In 2016, Science News magazine named him one of “10 Scientists to Watch” for his work on TSP. Oveis Gharan will collect his latest honor virtually during the upcoming annual meeting of the EATCS, the International Colloquium on Automata, Languages and Programming (ICALP 2021), in July.
Read the EATCS announcement here, and learn more about the Presburger Award here.
Congratulations, Shayan!