For Shayan Oveis Gharan, progress on hard problems often comes via unexpected detours.
In theoretical computer science, the key to cracking tough problems is finding the right tools. Most researchers gravitate toward tools that match the problems they hope to solve, and some devote entire careers to mastering a few familiar techniques. But Shayan Oveis Gharan, a computer scientist at the University of Washington in Seattle, has never been content with the familiar. When he sticks with the same approach for too long, he gets restless.
“I’m not learning anything new,” he said. “I’m just sort of staying where I am.”
Physically as well as intellectually, Oveis Gharan seems to have trouble staying still. Talk to him about his research, and he’ll grow increasingly animated, shifting constantly from one unorthodox position to another — first sitting cross-legged in an armchair, then hugging his knees to his chest, then turning sideways and draping his legs over the armrest.
Perhaps it’s fitting, then, that Oveis Gharan is renowned for his work on the traveling salesperson problem, a notoriously difficult computational problem about roaming from place to place. He’s also made major contributions to a seemingly unrelated subject: understanding the best way to choose randomly from a large collection of mathematical objects. For these efforts and others, Oveis Gharan has received the International Mathematical Union’s Abacus Medal, awarded every four years to a theoretical computer scientist under 40. The award committee cited his use of novel tools from far-flung reaches of mathematics that appear unrelated to computer science. It’s as if a creative carpenter discovered that for some tasks a stethoscope works better than a saw.
“This is what a lot of the brilliant, great researchers do,” said Anna Karlin, a colleague and collaborator of Oveis Gharan’s at the University of Washington. “They connect things that are seemingly disconnected.”
Oveis Gharan is known for his energy and enthusiasm. “He’s incredibly fun to work with,” said his colleague Anna Karlin. “He’s a believer that you can make progress.”
Researchers who draw connections between disparate fields often cultivate their breadth of knowledge at the expense of deep engagement with any one subject. But not Oveis Gharan. For all his restless energy, he has the patience to sit with hard problems for years and attend to every technical detail of a long and complex proof.
“Shayan can kind of do it all,” said Jonathan Leake, a mathematician at the University of Waterloo who collaborates with Oveis Gharan. “I don’t know how he does it, honestly.”
Restless Optimism
Oveis Gharan’s chosen field of theoretical computer science centers on understanding algorithms, the mathematical procedures that computers use to accomplish specific tasks. Some researchers seek to map the limits of computation, by identifying problems that are too hard for even the cleverest algorithms. Others aim to push the boundaries of what algorithms can do. Oveis Gharan, an optimist at heart, falls squarely in the latter group.
“I’m on the positive side,” he said. “I like to say things are possible.”
Oveis Gharan is slender and sprightly, with unruly black hair and an irrepressible smile. His enthusiasm for his work is palpable, even infectious. “He’s incredibly fun to work with,” Karlin said. “He’s a believer that you can make progress.”
Recent events outside mathematics have tested Oveis Gharan’s characteristic optimism. In the past 12 months alone, his fellow Iranians have endured a violent crackdown on protests by their government; a raft of punitive economic sanctions imposed by the United States, the European Union, and the United Nations; and airstrikes by the U.S. and Israel whose targets included Sharif University of Technology in Tehran, Iran’s leading science and engineering school and Oveis Gharan’s alma mater.
“I see a lot of my old friends and family members suffering,” he said. “It gets hard to work.”
Oveis Gharan was born in the historic city of Isfahan in 1986 during another difficult time in his country’s history — the eight-year war with Iraq. His father was a civil engineer, and his mother, Fatemeh Khoei, was a middle-school biology teacher who earlier in life had reluctantly set aside her aspirations to study mathematics.
“At the time she was growing up, the culture was ‘girls should not get into math,’” Oveis Gharan said. “She didn’t have the opportunity.”
Instead, Khoei pushed her children to excel academically. Shayan was the youngest of five. He grew up watching his siblings, who range in age from six to 13 years older than he is, studying math, science, and medicine. As a boy, he was shy but had a competitive streak, and he was eager to prove that he could match his talented siblings’ accomplishments. “He was always comparing himself with older kids,” Khoei said in Farsi as her daughter Shadi translated.
Oveis Gharan is an optimist at heart. “I’m on the positive side,” he said. “I like to say things are possible.” Chona Kasinger for Quanta Magazine
Shayan was especially close to his brother Shahab, who studied computer science and competed in the International Olympiad in Informatics, a contest of math and programming skill, in the late 1990s. When Shayan started middle school, Shahab gave him a book of math puzzles, and he was instantly hooked. “It brought a sparkle to his mind to dig much, much deeper,” Shahab recalled. Shayan went on to compete in the Olympiad himself and won a gold medal in 2004.
Though it was the mathematical side of computer science that initially drew him to the field, Oveis Gharan studied computer engineering as an undergraduate at Sharif University, thinking it would offer a more stable career. In his first year, he began dating a fellow engineering student, Farnaz Ronaghi, and the two bonded over hikes in the mountains and wide-ranging conversations about philosophy and religion. They married at the end of college and soon faced a big decision about their future.
Oveis Gharan, who’d found work in the computer graphics industry, was inclined to stay in Iran, but Ronaghi wanted to continue her education abroad, and she convinced him to apply to graduate school. Both were admitted to Stanford University, where Oveis Gharan’s sister Shadi, the first in the family to emigrate, had just received her doctorate in electrical engineering. Shadi encouraged her still-reluctant brother to accept the offer — theoretical research would open new opportunities, she said, and he could always go back to a software job if he didn’t like it.
As it happened, a taste of research was all that Oveis Gharan needed to rekindle his love of mathematics.
Tours and Detours
Graduate school was where Oveis Gharan first encountered the traveling salesperson problem, the famously thorny question that he would wrestle with on and off for the next decade. It asks: Given any map of cities connected by a road network, what is the shortest round-trip route that passes through every city? Researchers think there’s no way to design an algorithm that can quickly find the exact solution for all possible maps. Instead, they aim to design algorithms that always find relatively short round-trip tours — reasonable approximations of the ideal route.
Oveis Gharan in his office at the University of Washington. Chona Kasinger for Quanta Magazine
In 1976, the mathematician Nicos Christofides devised a simple algorithm that yields a remarkably good approximation: It always finds a round-trip tour that’s at most 50% longer than the shortest possible route. (In the Soviet Union, Anatoliy Serdyukov came up with the same idea independently around the same time.) Ever since then, researchers have tried in vain to craft an algorithm that’s guaranteed to get closer to the exact solution.
In Oveis Gharan’s first year of graduate school, he helped his adviser Amin Saberi and other researchers design an algorithm for the “asymmetric” version of the traveling salesperson problem, in which maps can include one-way roads. Bolstered by that success, Oveis Gharan, Saberi, and the computer scientist Mohit Singh set out to prove that a similar method could beat Christofides’ record for the original symmetric problem.
As a second-year graduate student, Oveis Gharan quickly took charge of the effort. Saberi was used to giving students feedback on their ideas, but in his meetings with Oveis Gharan, he often found himself on the receiving end.
“In his own cheerful and polite way, [he’d] explain in the first 10 minutes of the meeting why the approach I suggested is unlikely to work,” Saberi said. “Then for the other 15 minutes, we would be discussing what he thought would be the right way.”
Researchers who study the traveling salesperson problem use mathematical representations of maps called graphs: networks in which nodes represent cities, and the links between them (called edges) represent roads. The first step in many algorithms, including Christofides’, is to find a specific kind of path through the graph called a spanning tree, which touches every node but contains no closed loops. Every graph has many possible spanning trees.
Mark Belan/ Quanta Magazine
Once you have a spanning tree, you can transform it into a round-trip route by adding edges or doubling back at dead ends. A key question for traveling salesperson algorithms is which of the many spanning-tree options to start with. Christofides’ algorithm picks out the one that’s shortest when you add up the lengths of all its edges. This is usually a good starting point. But for some graphs, the shortest spanning tree has many dead-end branches, so the process of transforming it into a round-trip tour can actually make the route much longer.
Oveis Gharan and his colleagues hoped to avoid these extra-long routes by first harnessing randomness to select a promising spanning tree, and then transforming it into a round-trip tour. Randomness had been the crucial ingredient in their algorithm for the asymmetric traveling salesperson problem, and they quickly worked out how to adapt that algorithm to the symmetric problem. They thought that this approach would be able to beat Christofides’ algorithm — intuitively, if you use randomness to choose a spanning tree, you won’t get stymied by cases where the shortest spanning tree turns out to be a bad choice. The more randomness, the better.
But turning this intuition into a rigorous proof was not easy. They needed a way to analyze mathematical expressions that specify the chance of getting each possible spanning tree. Even a relatively small graph can have billions of spanning trees, and it’s hard to reason about problems with so many possibilities.
The key was to transform those mathematical expressions into formulas called polynomials, in which variables are multiplied and added together. Rewriting the problem in this unusual form, with one added term for each possible spanning tree, allowed Oveis Gharan to analyze it with a new set of mathematical tools. “Then you translate your finding to the setting of the original problem,” he said. “It’s like a detour.”
Armed with these new tools, Oveis Gharan and colleagues proved that their new algorithm outperformed Christofides’ classic algorithm for an important special case of the traveling salesperson problem. They suspected that there was more to the story — that the new algorithm would actually be superior in the most general case. It would take a few more detours to prove it.
Brick by Brick
Oveis Gharan’s early work on the traveling salesperson problem was the first instance of a pattern that would recur throughout his career. He doesn’t hesitate to plunge into the literature on unfamiliar subjects, from probability theory to statistical physics to abstract math like algebraic geometry, and pluck out new tools to use in his own work.
“He always liked to read a million papers,” Ronaghi said. “He has an infinite amount of capacity for learning new concepts.”
Yet to hear Oveis Gharan tell it, research is often a struggle. “It has a lot of ups and downs, mostly downs,” he said. “You always think, ‘Can I ever come up with something that doesn’t fail?’” He rarely experiences the eureka moments that abound in popular portrayals of mathematical research. Instead, working on a proof feels like building a house one brick at a time. There are many ways to assemble the pieces, and only when the whole thing is nearly complete can you be sure that it’s structurally sound.
“You put these bricks on top of each other,” he said. “You never know if you’re doing it the right way.”
Oveis Gharan often finds it helpful to busy himself with another activity while mulling over math problems. In graduate school, his preferred pastime was another sort of brick stacking — he played so many games of Tetris at his desk that a professor with a nearby office once asked him when he actually did his work. At one point the solution to a problem he’d been wrestling with appeared to him in a dream, but he didn’t have a notebook on hand when he woke up to jot down the idea before it faded. For some time after that, he would concentrate on mathematics as he was falling asleep, in hopes of spurring another nocturnal breakthrough, without success. “I would end up waking up with a headache,” he said.
Oveis Gharan says he does some of his best thinking when he’s surrounded by nature.
In graduate school, Oveis Gharan mostly worked alone, checking in with mentors periodically to exchange ideas. Since then, he’s preferred close collaborations that involve frequent marathon brainstorming sessions. In 2013, he struck up what would become a long and fruitful collaboration with Nima Anari, a fellow alumnus of the Iranian Informatics Olympiad team who was a graduate student at the University of California, Berkeley when Oveis Gharan arrived on campus for a postdoctoral fellowship.
Together, Oveis Gharan and Anari used polynomial methods to make further progress on the asymmetric traveling salesperson problem and settle a longstanding open question in graph theory. They then grew interested in a fundamental question about algorithms that harness randomness. These algorithms assume that you can easily pick a random item from a collection of mathematical objects — a task that statisticians call sampling. But how exactly do you get that random sample?
Chain Reaction
Sampling problems are common in the real world. Card games are a classic example: You want your deck to be in a random order before you deal. When you repeatedly shuffle a deck to randomize it, you’re essentially running a type of sampling algorithm called a Markov chain.
Every Markov chain algorithm starts with one item from a large collection of mathematical objects, such as all the possible ways to order a given deck, or all the possible spanning trees of a given graph. Then the algorithm repeatedly tweaks this object by introducing a bit of randomness — in the case of spanning trees, each tweak deletes a random edge and adds another to get a new spanning tree. Repeat this process until that spanning tree no longer bears any trace of the tree you started with. The output of the last step is your random sample.
To be confident that the sample is truly random, though, you need to know how many times to repeat the process — or, in other words, how long to run the Markov chain. This quantity is called the mixing time, and it depends on the mathematical structure of the sampled objects.
In 1989, the computer scientists Milena Mihail (who died in April 2026) and Umesh Vazirani made an important conjecture about sampling mathematical objects related to spanning trees called matroid bases — a task that has many applications in computer science and beyond. They proposed that a simple Markov chain could accomplish this sampling task, but they didn’t know how to establish that the Markov chain would have a short enough mixing time. For years, many researchers tried and failed to prove their conjecture. “Every technique people had tried before just didn’t get us there,” said Daniel Spielman, a computer scientist at Yale University who wrestled with the problem himself in the 1990s. “We needed some new math.”
Oveis Gharan and Anari teamed up with new collaborators and supplied that new math in 2018. Working with the mathematician Cynthia Vinzant, they translated the matroid basis sampling problem into the language of polynomials, just as Oveis Gharan had done when working on the traveling salesperson problem, and identified the key feature shared by those polynomials. The result was an important breakthrough in pure mathematics in its own right, and it provided them with a useful new tool. Joined by Oveis Gharan’s student Kuikui Liu, the team then used this key feature with other seemingly unrelated tools to finally prove the matroid basis sampling conjecture, 30 years after it was first proposed.
“It was a stunning result,” Vazirani said. “It really did seem like a piece of magic.”
Oveis Gharan (right) in 2005, with his siblings (from left) Shahab, Shahram, Sheida, and Shadi. Courtesy of Shayan Oveis Gharan
The team’s landmark proof sparked a revolution in the study of sampling algorithms. Oveis Gharan, Anari, and Liu later developed a more general framework for identifying cases where Markov chains mix rapidly, among them mathematical models of materials that have long interested physicists. “After that, it felt like everyone and their adviser jumped into the pool,” Spielman said. “It’s really changed how the field works.”
Return Journey
In late 2018, as the sampling revolution was just beginning, Oveis Gharan was already itching for another challenge. He decided it was time to return to the traveling salesperson problem, where his intellectual journey had started a decade earlier. He’d picked up many mathematical tools on his travels in the intervening years. Now, he hoped to use those tools to prove that the algorithm he’d helped design as a graduate student would beat Christofides’ algorithm for the most general version of the problem.
“There’s a certain amount of fearlessness there, to say, ‘I’m going to take this on where everybody else has failed,’” said David Williamson, a veteran traveling salesperson researcher at Cornell University.
A decade after it first captured his interest, Oveis Gharan returned to the traveling salesperson problem in late 2018. Chona Kasinger for Quanta Magazine
Oveis Gharan began working on the problem with Karlin and a new graduate student, Nathan Klein. They devised new techniques for handling tricky graphs with a lot of overlap between regions that the algorithm needed to analyze separately. Combining those techniques with Oveis Gharan’s polynomial methods, they resolved another important special case in the spring of 2019 and finally conquered the most general version of the problem in December of that year — breaking the record that Christofides’ algorithm had held for over 40 years. It took them another seven months to double-check every detail of the proof and write up the dense 90-page paper describing their result.
Saberi, who’d first introduced Oveis Gharan to the traveling salesperson problem, was stunned by his former student’s achievement. “For me, it was like the Wright brothers” cobbling together a primitive plane, he said, “then seeing something akin to a Boeing-747 10 years later.”
Since landing at the University of Washington in 2015, Oveis Gharan has settled into life in Seattle with Ronaghi, who works as the chief technology officer of a start-up she founded as a graduate student. He keeps notebooks stashed throughout their house, in case inspiration strikes at odd hours, but he’s grown better at setting work aside, especially when spending time with their 10-year-old son Faraz. “Shayan has an impressive, impressive ability just to play,” Ronaghi said. “His brain can have fun, like a little kid, and not take it too seriously.”
Even when Oveis Gharan isn’t working, though, the competitive spirit that animated his childhood sometimes comes through. When the Covid-19 pandemic hit, he discovered a passion for cooking, and he approaches that hobby with the same perfectionist attitude that he brings to the rest of his work, especially when he’s hosting.
“My kids believe that he’s the best cook in the world,” his sister Shadi said. “I’m like, ‘Dude, relax, you don’t have to be the best in everything.’”
