Daniel Lokshtanov Receives NSF Award for Algorithm Research
Tuesday, September 23, 2025
by Cameron Walker (from UCSB Robert Mehrabian College of Engineering)
UC Santa Barbara computer science professor and vice chair of the Department of Computer Science Daniel Lokshtanov has received funding from the National Science Foundation (NSF) to support collaborative work to develop a structural theory for quasi-polynomial time algorithms. The $800,000 award, given to Lokshtanov and his colleague Maria Chudnovsky at Princeton University through the NSF’s Algorithmic Foundations program, “supports potentially transformative projects in the theory of algorithms,” according to the NSF.
"Daniel Lokshtanov's work in quasi-polynomial time algorithms will provide important insights into the foundations of computer science," said Divyakant Agrawal, distinguished professor and chair of the Department of Computer Science. "We are very proud that he is part of our department at UCSB, and congratulate him on his NSF award, which recognizes and supports this fundamental research."
Lokshtanov, who is also a visiting professor at the University of Bergen in Norway, studies the theory behind algorithmic efficiency — which has many practical applications. “When you run your program on your computer, you want it to be fast. You don't want to sit there and wait for minutes or hours or years,” he said. “You want your computer to boot fast. You want your web pages to load quickly. When you ask Google for the fastest way to get from A to B, you don't want the time it takes to answer to be longer than the time it takes for you to get there."
How quickly a program can do this depends on how much data it has to wrangle to solve a problem, and the complexity of the problem itself. Computer scientists are particularly interested in problems that can be solved in a category called polynomial time, in which the time needed to solve a problem grows in a way that’s considered manageable with an increase in the amount of data. For example, in a soccer tournament in which each team needs to play every other team once, if you have five teams, there will be ten matches; if you have fifty teams, there will be one thousand two hundred twenty-five matches; the number of matches will continue to grow as the number of teams grows, but such an increase is still thought to be reasonable and efficient. On the other hand, some problems explode exponentially as you add
more data. If you’re trying to break open a safe with a three-digit code, there are a thousand possibilities, but if that safe has a ten-digit code, the number of possibilities rises to ten billion!
With the NSF award, Lokshtanov and Chudnovsky, at Princeton, will investigate the efficiency of algorithms called quasi-polynomial time algorithms. “These kinds of algorithms fall in between: they're neither so slow that they’re really, really inefficient, but they're also not quite fast enough enough to be in the category of polynomial time,” he said. They will be looking at whether these quasi-polynomial algorithms can be useful for solving particular graph problems that have yet to be solved by polynomial-time algorithms.
One of the graph problems that they will be working on is called the Independent Set Problem. In a social media network, the Independent Set Problem looks for the largest number of people who are not connected to each other. So far, no one has solved this type of problem using polynomial time algorithms; in fact, Lokshtanov said, “we believe that such an algorithm doesn't exist.” But approaching these problems with slightly slower algorithms in mind could provide a new perspective. Using quasi-polynomial time algorithms, Lokshtanov said, “allows us to look at these graph problems from a slightly different perspective, which lets us prove statements that people wouldn’t have thought to try to prove before.”
Lokshtanov received his PhD in computer science from the University of Bergen, then spent two years as a Simons Postdoctoral Fellow at University of California at San Diego. He has received the Meltzer Prize and the Nerode Prize, as well as a previous research grant from the NSF for his work on algorithms and structural graph decompositions, a way of analyzing large or complex graphs. “I like to joke that I’m a mathematician cosplaying as a computer scientist. A lot of the math that I want to do is done under the computer science umbrella, and then has implications for programming in computer science,” Lokshtanov said. “And graph theory and graph algorithms are a cornerstone of computer science.”
While the focus of Lokshtanov’s most recent award is the theoretical underpinnings of quasi-polynomial time graph algorithms, in some cases, the work evolves into real-world advancements in computer science. “Often, when you're working on problems like these, you end up with algorithmic ideas that can be reused in practical applications,” he said. “We’re not trying to hide from those opportunities.”