Take a generous helping of mathematical brilliance, cover it in copious amounts of curiosity about the most vexing problems underpinning computer science, add a generous dash of humility, and what do you get?
Shayan Oveis Gharan, a professor in the Allen School’s Theory of Computation group, combines all the essential ingredients of a trailblazing researcher who, as his colleagues will attest, also happens to be a genuinely nice guy. The combination has also proved to be a genuine recipe for success, as he has racked up a series of accolades in theoretical computer science since he arrived at the University of Washington in 2015. His most recent honor, the Stephen Smale Prize from the Society for the Foundations of Computational Mathematics (FoCM), celebrated Oveis Gharan’s “breakthrough results on the applications of algebraic and spectral methods to the design of algorithms and to combinatorial optimization” that have made him “the architect of surprising and profound discoveries on foundational problems in computing.”
Oveis Gharan began acquiring the building blocks of those career triumphs as a middle school student in Iran, when he encountered the book “Mathematics of Choice: How to Count without Counting” by the Canadian-American mathematician Ivan Niven. Under Niven’s written tutelage, the young Oveis Gharan learned how to quickly count combinatorial objects — say, the number of ways one could assemble a basketball team consisting of 10 players and a captain from a class of 30 students — on paper. The lesson was a slam dunk, and counting problems still comprise a major portion of his research years later — only now, he’s designing computer algorithms to handle more sophisticated problems than the possible permutations with himself at point guard.
Later, as he prepared to do battle in regional and world informatics competitions, a teenaged Oveis Gharan practiced with hundreds of combinatorial and graph theoretic problems drawn from past Russian Mathematics Olympiads. That practice paid off, as he took home a silver medal from the 2003 Central European Olympiad; a year later, he won gold at the International Olympiad.
“Those experiences are the backbone of most problem-solving techniques I still use today,” Oveis Gharan noted, pointing out that old approaches can come in handy when it comes to new problems. It’s one of the aspects he loves most about his chosen line of work.
“One of the amazing characteristics of research in discrete mathematics and combinatorics is that there is rarely a unified theme to approach hard problems,” he explained. “One often needs to cook up a new method from scratch. So in one sense, it feels like we are going to fight with a challenging problem empty-handed, but in reality, previous work on related problems can offer a menu of ideas with which to approach this other problem.”
One challenge that Oveis Gharan found he could really sink his teeth into is the infamous Traveling Salesperson Problem, which he first encountered over a decade ago as a Ph.D. student at Stanford University. There, he and his colleagues set out to design an improved approximation algorithm for metric TSP.
At first, the team thought they had the solution — until they realized they didn’t.
“About halfway through we figured some of our intermediate conjectures were wrong,” Oveis Gharan recalled. “So, we made the problem simpler and instead only managed to prove that the algorithm breaks the long-standing barrier for a special family of metrics called ‘graph metrics.’ It wasn’t until two years ago that I and another group of co-authors finally achieved a result for all metrics.”
The aforementioned result was the first performance improvement in metric TSP in more than 40 years. Along the way, Oveis Gharan contributed to what co-author and Allen School professor Anna Karlin has described as a “deep mathematical machinery” mixing elements of graph theory and probability theory that researchers have since applied to other open problems. Among the tools in this expanded mathematical toolbox were the use of maximum entropy sampling, new theorems related to the geometry of polynomials, Strong Rayleigh probability distributions and negative dependence, and new insights into the combinatorial structure of the minimum and near-minimum cuts of a graph. Oveis Gharan and his co-authors, including Ph.D. student Nathan Klein, subsequently used the latter to build on their initial result by showing the integrality gap of the subtour linear programming relaxation for TSP is below 3/2 last year.
What is it about TSP that he finds so alluring? As Oveis Gharan explains it, TSP is different from most computational problems encountered by theoreticians, like the graph coloring problem, that require one to satisfy a range of local constraints. With TSP, one has to satisfy both a set of local constraints and a global constraint — connectivity — simultaneously.
“Oddly enough, each of these two sets of constraints is easy to satisfy optimally on their own, but the challenge is to satisfy both,” he said. “The quest in studying TSP is that you want to construct solutions which are locally correct while globally connected.”
For Oveis Gharan, satisfying that dual challenge is where the rubber meets the road.
”Think of a driver going from Seattle to San Francisco. They need to keep an eye on the road to make sure they are ‘locally’ driving safely — i.e., not ramming into the next car and not driving out of bounds,” he said. “But they also need to keep the bigger picture of the route in mind, choosing the right highway at every junction. Now in this example, perhaps, the bigger picture is easy to keep in mind when there’s only a single highway, I-5, running all the way south. But imagine how difficult it would be with millions of possible roads to choose from, and no GPS! That is similar to the dilemma in designing an algorithm for TSP.”
Despite his devotion to that problem, Oveis Gharan is also driven to tackle other challenges. For example, he is widely known for his work analyzing the Markov Chain Monte Carlo (MCMC) technique for sampling from high dimensional distributions and as a method for studying large, complicated sets. As part of that work, Oveis Gharan and his collaborators — including former student Kuikui Liu (Ph.D., ‘23), who will join the faculty of MIT this fall — developed the theory of spectral independence, a revolutionary approach for approximate sampling of Markov chains that has implications for computational biology, machine learning, physics and more.
Oveis Gharan and his colleagues leveraged that approach to produce the first efficient approximation algorithm for counting the bases of a matroid and simultaneously proved a 30-year-old conjecture concerning the minimum edge expansion of the bases exchange graph of any matroid. In another paper of the same series, he and his co-authors answered another open question that had gone unanswered for nearly three decades by proving that an algorithmic tool used in statistical physics called Glauber dynamics mixes in polynomial time to generate a random independent set for any graph up to the phase-transition threshold.
The aforementioned work relates to expander graphs — which, in Oveis Gharan’s view, are “one of the most extraordinary inventions in mathematics.” He is keen to further explore the theory of high-dimensional expanders, which have numerous practical applications in computing.
“On one hand, these graphs are as sparse as, say, a cycle; on the other hand, they preserve almost all properties of a complete network,” Oveis Gharan explained. “If one wants to build a sparse routing network that will be as reliable as possible against node or connection failures, the best design is to use an expander graph. High dimensional expanders are a generalization of expander graphs to hypergraphs, which have been a subject of intense study over the last decade leading to several breakthroughs, from improved analysis of MCMC algorithms, to the construction of new locally testable codes.”
To someone whose work is typically celebrated in optimization and algorithm design circles, the Smale Prize came as a pleasant surprise.
“Although not the community in which I normally publish my research, I am truly honored and amazed that my work has been recognized by leaders in computational mathematics,” he said. “This certainly motivates me and my research group to pursue a deeper understanding of problems at the intersection of math, computer science and efficient computation.”
The Smale Prize — named for Stephen Smale, one of the founding members of FoCM — is awarded every three years. The organization formally honored Oveis Gharan, who joins rarefied company as only the fifth recipient since the prize’s inception, during its annual conference in Paris last month.