Breaking new ground in algorithmic theory

From powering search engines to securing data and optimizing networks, algorithms underpin nearly every aspect of modern technology. Understanding how efficiently they can solve problems — and where those limits lie — is one of computer science’s most fundamental challenges.

UC Santa Barbara computer scientist Daniel Lokshtanov is advancing fundamental understanding of computational efficiency through groundbreaking research on quasi-polynomial time algorithms, supported by a recent $800,000 award from the National Science Foundation’s Algorithmic Foundations program. His work focuses on a class of problems that lies between efficiently solvable and computationally intractable — a gray area that holds key insights into how computers process complexity. 

By developing a new structural theory, Lokshtanov aims to redefine what kinds of problems can realistically be solved, with potential ripple effects across fields from cryptography to artificial intelligence.

Lokshtanov’s NSF-funded collaboration with Maria Chudnovsky of Princeton University is part of a national effort to strengthen the theoretical foundations of computer science by exploring how algorithms can be made faster, smarter and more broadly applicable.

“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.”

Algorithmic efficiency has many practical applications. “When you run your program on your computer, you want it to be fast,” said Lokshtanov, who is also a visiting professor at the University of Bergen in Norway.  You don’t want to sit there and wait for minutes or hours or years. 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. 

As an example, in a soccer tournament in which each team needs to play every other team once, if you have five teams, there will be 10 matches; if you have 50 teams, there will be 1,225 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 10-digit code, the number of possibilities rises to 10 billion.

With the NSF award, Lokshtanov and Chudnovsky 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 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 doctorate 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 NSF research grant 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.”