Shayan Oveis Gharan has won the Abacus Medal for using tools from across mathematics to boost the power of algorithms.
The prestigious Abacus Medal, awarded by the International Mathematical Union every four years to exceptional theoretical computer scientists under the age of 40, has been presented to Shayan Oveis Gharan of the University of Washington. The award specifically recognizes his groundbreaking work in leveraging disparate mathematical disciplines to enhance algorithmic capabilities, a testament to his innovative approach to complex computational challenges. Gharan’s research has notably advanced our understanding of the notoriously difficult Traveling Salesperson Problem (TSP) and shed new light on the intricacies of random sampling from large mathematical structures.
The Architect of Algorithmic Innovation
In the realm of theoretical computer science, the quest for elegant and efficient solutions to computational puzzles often hinges on the judicious selection and application of mathematical tools. While many researchers dedicate their careers to mastering a specific set of techniques, Shayan Oveis Gharan has carved a distinct path, characterized by a restless intellectual curiosity and a remarkable ability to bridge seemingly unrelated fields. This interdisciplinary approach, celebrated by the Abacus Medal committee, has enabled him to develop novel algorithms and proofs that push the boundaries of what is computationally feasible.
Anna Karlin, a colleague and collaborator of Gharan’s at the University of Washington, highlighted his unique talent: "Brilliant researchers connect things that appear disconnected. Shayan does this exceptionally well." This ability to forge connections across diverse mathematical landscapes has been a hallmark of Gharan’s career, allowing him to tackle problems that have eluded others.
A Journey Through Complexity: The Traveling Salesperson Problem
At the heart of much of Gharan’s celebrated work lies the Traveling Salesperson Problem (TSP). First posed in its modern form in the 1930s, the TSP asks for the shortest possible route that visits a given set of cities and returns to the origin city. Despite its simple formulation, finding the optimal solution for even a moderate number of cities is computationally intractable, belonging to the class of NP-hard problems. This means that as the number of cities increases, the time required to find the exact solution grows exponentially, rendering brute-force computation impossible for real-world scenarios.
For decades, researchers have focused on developing approximation algorithms that can efficiently find routes that are close to the optimal, rather than precisely optimal. A significant milestone was achieved in 1976 when Nicos Christofides developed an algorithm that guarantees a tour no more than 50% longer than the absolute shortest route. This algorithm, along with independent work by Anatoliy Serdyukov, set a benchmark that has proven exceptionally difficult to surpass.
Gharan’s engagement with the TSP began during his graduate studies. In collaboration with his advisor Amin Saberi and Mohit Singh, he contributed to developing an algorithm for the "asymmetric" version of the TSP, where road networks might include one-way streets. This early success fueled his ambition to improve upon Christofides’ bound for the more common "symmetric" TSP.
His approach involved a departure from traditional methods. Instead of solely focusing on the shortest spanning tree (a fundamental structure used in TSP algorithms), Gharan and his colleagues proposed leveraging randomness to select a more promising spanning tree. The intuition was that a randomly chosen tree might avoid the pitfalls of shortest spanning trees that could lead to inefficient tours due to their specific structures.
However, translating this intuitive advantage into a rigorous mathematical proof proved arduous. The challenge lay in analyzing complex probability distributions over vast numbers of possible spanning trees. Gharan’s ingenuity in transforming these probability distributions into polynomial equations, a technique borrowed from abstract mathematics, provided a novel lens through which to analyze the problem. This detour through polynomial methods, as he described it, allowed him to harness a new suite of mathematical tools.
This innovative application of polynomial analysis led to a significant breakthrough, demonstrating that their randomized algorithm outperformed Christofides’ method for a crucial special case of the TSP. While they suspected broader applicability, further exploration was needed. This initial success laid the groundwork for what would become a decade-long pursuit to definitively break the Christofides’ bound in its most general form.
The Revolution in Random Sampling
Beyond the TSP, Gharan’s research has profoundly impacted the field of random sampling, particularly through his work on Markov chains and their mixing times. Sampling algorithms are crucial for many computational tasks, from simulating complex systems to ensuring fairness in randomized algorithms. A common method for sampling involves using a Markov chain, which iteratively moves through a space of possible outcomes, gradually converging to a desired random distribution. The efficiency of this process is determined by its "mixing time"—the number of steps required for the chain to effectively forget its starting point and reach a state representative of the underlying probability distribution.
A pivotal moment in this area came with the conjecture by Milena Mihail and Umesh Vazirani in 1989 concerning the sampling of matroid bases, a concept with wide-ranging applications in areas like network design and optimization. They proposed a specific Markov chain for this task but lacked the mathematical tools to prove its efficient mixing time. For nearly three decades, this conjecture remained an open problem, with numerous researchers attempting to crack it without success.
Gharan, in collaboration with Nima Anari and Cynthia Vinzant, revisited this problem. Echoing his strategy for the TSP, he again employed polynomial methods to reframe the sampling problem. This transformation allowed them to identify a critical property of the relevant polynomials, which, when combined with other advanced mathematical techniques, finally led to a proof of the matroid basis sampling conjecture in 2018. This result, described as "stunning" and "like a piece of magic" by Vazirani, was a landmark achievement, effectively providing a new framework for analyzing the mixing times of Markov chains.
The impact of this work was immediate and far-reaching. It ignited a "revolution in the study of sampling algorithms," as described by Daniel Spielman, a computer scientist at Yale University. Gharan, Anari, and their student Kuikui Liu further generalized their findings, developing a broader framework for identifying rapidly mixing Markov chains. This work found applications in diverse fields, including the modeling of materials, which has long been of interest to physicists. The widespread adoption of these new techniques has fundamentally reshaped the landscape of algorithmic research in sampling.
A Return to Roots and Further Triumphs
Fueled by the success of his work on sampling, Gharan felt compelled to revisit the Traveling Salesperson Problem. By late 2018, he had accumulated a wealth of new mathematical tools and insights from his explorations into other areas of computer science and mathematics. He embarked on a mission to prove that the randomized algorithm he had helped develop years prior could indeed surpass Christofides’ record in the most general case.
This endeavor was not for the faint of heart. David Williamson, a seasoned TSP researcher at Cornell University, noted Gharan’s "fearlessness" in tackling a problem where many had previously failed. Working alongside his colleague Anna Karlin and a graduate student, Nathan Klein, Gharan developed innovative techniques to handle particularly complex graph structures. These new methods, combined with his established expertise in polynomial techniques, allowed them to resolve another critical special case of the TSP in 2019.
The ultimate triumph came in December 2019, when Gharan and his team finally conquered the most general version of the Traveling Salesperson Problem. This achievement, announced in 2020, broke the over 40-year-old record held by Christofides’ algorithm. The culmination of this work was a comprehensive 90-page paper detailing their rigorous proof, a testament to the depth and complexity of the problem and their solution. Amin Saberi, who first introduced Gharan to the TSP, marveled at the progress, likening it to the evolution from the Wright brothers’ early aircraft to a Boeing-747 in just a decade.
A Life of Intellectual Exploration and Personal Balance
Shayan Oveis Gharan’s journey is marked by a relentless pursuit of knowledge and a unique ability to navigate complex intellectual terrain. Born in Isfahan, Iran, in 1986, he grew up in a family that valued academic achievement. His mother, Fatemeh Khoei, had to set aside her own mathematical aspirations due to societal norms of the time, but she instilled a strong drive for excellence in her five children. Gharan’s older brother, Shahab, who competed in the International Olympiad in Informatics, served as an early inspiration, introducing Shayan to the captivating world of math puzzles. This early exposure ignited a passion that would define his academic and professional life.
His path to theoretical computer science was not entirely linear. After excelling in the Iranian Informatics Olympiad, he pursued computer engineering as an undergraduate at Sharif University of Technology. However, the allure of research, particularly its mathematical underpinnings, soon became irresistible. A pivotal decision to pursue graduate studies abroad with his wife, Farnaz Ronaghi, led him to Stanford University, where his sister Shadi, already a doctoral candidate, encouraged his foray into theoretical research.
Since joining the University of Washington in 2015, Gharan has found a balance between his demanding research career and his personal life. He and Ronaghi, now a successful CTO, are raising their son, Faraz. Ronaghi notes his impressive ability to switch between intense intellectual focus and genuine, childlike playfulness, a trait that likely fuels his creativity. Even in his leisure activities, such as his newfound passion for cooking, Gharan exhibits a characteristic drive for perfection, a testament to his deeply ingrained competitive spirit.
The Abacus Medal recognizes not just Gharan’s individual achievements but also his broader impact on the field. His willingness to venture beyond conventional boundaries, drawing insights from diverse mathematical disciplines, exemplifies the spirit of innovation that drives scientific progress. His work on the Traveling Salesperson Problem and random sampling has not only solved long-standing challenges but has also provided powerful new tools and frameworks that will undoubtedly inspire future generations of researchers. Shayan Oveis Gharan’s career is a compelling narrative of intellectual curiosity, rigorous problem-solving, and the profound beauty that emerges when disparate ideas converge.
