After completing his three-year term as a Research Assistant Professor at TTIC in 2020, Professor Thatchaphol Saranurak joined the faculty at the University of Michigan. Prof. Saranurak is an Assistant Professor in the Computer Science and Engineering Division, specializing in graph theory and dynamic graph algorithms.
“You can represent anything using a graph,” said Prof. Saranurak. “For example, if you talk about a road network, you might want to go from city A to city B quickly, and that is just a shortest-path problem in a graph algorithm.” Dynamic graph algorithms are problems where the graph itself changes. If you have a road map, and one road ends up having more traffic, the route has changed and the user may want a new path that is shorter. Instead of recomputing the entire database from scratch, this type of algorithm creates a faster way to update the data and answer the query as to the new shortest path.
Prof. Saranurak became interested in this field even before beginning his PhD at the KTH Royal Institute of Technology. “Before I started my PhD, there was a paper titled ‘Dynamic graph connectivity in polylogarithmic worst case time’ by Kapron, King, and Mountjoy, where they asked a similar question about dynamic shortest-path algorithms. Now they ask about connectivity, and they get a much faster algorithm. The algorithm is so beautiful, and it inspired me a lot. I kind of switched the field a bit from algebraic complexity theory to this more concrete, tangible area,” he said.
He chose to continue his career at the University of Michigan because there are several professors there who also work in the field of graph theory, as well as a number of students who share his research interests.
Being a RAP at TTIC helped him to prepare for a career in academia in a number of ways. “I really had a lot of freedom, and I feel that I became a more mature researcher during that time,” said Prof. Saranurak. He also enjoyed being able to conduct research and build connections with a variety of people, at both TTIC and the University of Chicago since they are located on the same campus.
“Sometimes I just knocked on Nati’s door (Prof. Nati Srebro), and asked him some questions about machine learning, so I think that that’s quite nice,” he said. That ability to create close connections with other researchers and spark conversations is a key component of research life at TTIC.
“I switched my field to graph theory and algorithms because of this dynamic connectivity problem that I find so beautiful and inspiring. You can ask if there is any path at all, from A to B, but that algorithm is randomized, and it might make an error. So we try to make it deterministic. This was my main project during my PhD, but I didn’t complete it. During the time when I was at TTIC, Prof. Julia Chuzhoy, Prof. Richard Peng, Prof. Danupon Nanongkai, Jason Li, Yu Gao and I made some progress toward this. We basically make it deterministic now, so that’s a long standing open problem that people have really wanted to do for like 30 years, and it’s now closed,” said Prof. Saranurak.
This research culminated in a paper titled “A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond.” An interscholastic research effort, this paper included work from professors and researchers at TTIC, Georgia Tech, Carnegie Mellon University, and the KTH Royal Institute of Technology. Prof. Danupon (KTH) was Prof. Saranurak’s PhD advisor. Closing this long-standing open problem with his colleagues at TTIC is one of the accomplishments that he is most proud of.
Since leaving TTIC, he has also made significant progress with the shortest-path algorithm. “People wanted to do the problem both fast and deterministic, and people could do it deterministic and not fast, or fast but not deterministic. But now we can do both, and that has a lot of applications,” he said. That research is evidenced in the paper titled “Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time,” co-written by Bernstein, Gutenberg, and Prof. Saranurak.
His advice to current RAP’s at TTIC is to cherish their time and use it as efficiently as they can. “It was just the best time, I enjoyed it so much. It is a rare opportunity that you have so little responsibility, and so much freedom. It’s very cool,” said Prof. Saranurak.
In his new role at the University of Michigan, he still enjoys conducting research. After becoming a faculty member, he realized just how much he enjoys teaching as well. He loves sharing his passion for research with students who are interested in the same areas, and being able to mentor them to succeed in their own research.
In the future, he hopes to drive more research in the area of dynamic graph data structure, and make graph algorithms even more relevant and practical. His main goals are to continue doing good research, and to enjoy teaching.