Breaking new ground in algorithmic theory

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."

About UC Santa Barbara

The University of California, Santa Barbara is a leading research institution that also provides a comprehensive liberal arts learning experience. Our academic community of faculty, students, and staff is characterized by a culture of interdisciplinary collaboration that is responsive to the needs of our multicultural and global society. All of this takes place within a living and learning environment like no other, as we draw inspiration from the beauty and resources of our extraordinary location at the edge of the Pacific Ocean.