Prof. Roditty's Lab
Prof. Liam Roditty, an Associate Prof. in the Department of Computer Science, studies both theoretical and practical aspects of computer science. One of his lab’s main areas of research is dynamic algorithms, which are algorithms that maintain certain information on a network (graph) that is being changed over time.
Roditty and his team also investigate problems that emerge in real world dynamic networks such as road networks, and the internet.
Although the area of dynamic algorithms has been a field of active research for the last three decades, there are still many remaining open problems. The most fundamental dynamic graph problems include dynamic connectivity and minimum spanning tree in undirected graphs, dynamic reachability in directed graphs, and dynamic shortest-paths.
Roditty and his group investigate these problems and others using both traditional and non-traditional dynamic update models. The non-traditional models are inspired both by real-world dynamic networks and by theoretical limitations that classical dynamic algorithms encounter in traditional models.
Among the non-traditional models, the group mainly focuses on both the dynamic subgraph model and the fault tolerant model (and their variants). In the dynamic subgraph model, the graph is maintained under vertex updates, as opposed to edge updates.
In each update, a vertex is either turned on or off, and queries refer to the subgraph induced on the vertices (such a model is closer to applications in networks of routers, where node faults may occur). The dynamic subgraph model is important since it is closely connected to dynamic problems in computational geometry.
In the fault tolerant model, Roditty and his group preprocess the input graph such that after any arbitrary d (edge or vertex) faults, a new output will be rapidly computed. For example, they preprocess an undirected graph into a spanner (i.e., another graph on the same vertex set with a similar shortest distance structure), such that after any dedge or vertex deletions, the spanner will still be a good spanner of the current graph.
This model, which is more restricted than the regular dynamic model, is much closer to real world dynamic networks. For instance, a road in a map network is more likely to be temporarily unavailable than to be deleted forever from the network. Roditty and his group investigate reachability, shortest paths, and other fundamental problems in this model.
While much of the work conducted by Roditty and his group lies in the theoretical realm, they also conduct experimental work to test the practical applications of their ideas. In effect, their research process represents a chain that begins with developing theoretical algorithms that outdo the previously known “best” algorithms and ends with exploring how the algorithm can be useful in real-world situations.
For instance, much of the lab’s work can be applied to driving directions, since a map is a graph that represents connections between cities that have a certain distance between them. When obtaining directions, the algorithm needs to calculate the optimal path by taking into account factors such as distance and time of day (traffic). By exploring several variants that influence identification of the optimal path, theoretical work in Roditty’s lab is paving the way for improving map generation.
Looking to the future
Roditty and his team plan to expand their testing of real world inputs, and to continue to bridge the gap between theoretical science and practical applications of their work. In addition, they aim to solve remaining open problems, such as bridging the gaps between the performance of algorithms for computing shortest paths in different networks.