Thatchaphol Saranurak earns NSF CAREER Award to study tackle problems in dynamic graphing algorithms

Thatchaphol Saranurak, assistant professor of computer science at the University of Michigan, has received a National Science Foundation (NSF) CAREER Award to solve open problems in graph theory by studying their inter-connections. The project is titled “Theory for Dynamic Graph Algorithms.”

Graphs, any group of nodes joined by edges, are one of the most natural representations of relationships between data. We graph the relationship between customers and their orders in commerce, between places in navigation, between individuals in genetics, and between abstract concepts in the study of knowledge generation. Nearly every branch of science relies on this representation, making the study of graph algorithms one of the key challenges in computing.

But in the era of the internet, social networks, and massive data generation, traditional graph algorithms struggle to keep up with with the constant updates being made to active databases. Changes to existing data and the constant generation of new data leads to a stream of new relationships in a graph representation, which can be costly and complex to recreate with these traditional methods.

Dynamic graph algorithms are a recent innovation that enable the maintenance of useful information, like a graph’s connectivity and the shortest path between nodes, even while changes are being made to the underlying data.

In his CAREER research, Saranurak will study the connections between these dynamic graph algorithms and a number of important open problems in graph theory, security, and optimization. His key areas of focus include:

• Developing generic techniques for dynamic algorithms that are robust against an adaptive adversary, drawing on fields like privacy, cryptography, and complexity theory
• Developing new sublinear time algorithms, graph sparsification, and graph decomposition techniques that will lead to breakthroughs in dynamic algorithms
• Making continuous optimization methods dynamic, and developing optimization tools for dynamic problems

“These are the holy-grail problems that have exponential upper and lower bound gaps,” Saranurak says. “Even partial progress should advance our understanding of the field and be useful as a subroutine for future algorithms.”