CAREER: Theory for Dynamic Graph Algorithms

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

Graphs are one of the most natural representations of relationships between data and are, hence, used in nearly every branch of science. Unfortunately, traditional graph algorithms are often no anymore viable because graphs in modern applications like†the internet/traffic/social networks are always evolving. To address this issue, dynamic graph algorithms research aims to design efficient methods for maintaining useful information (e.g., connectivity, shortest paths, matching) on graphs undergoing updates through time without wastefully recomputing answers from scratch after each update. In the last few years, several breakthroughs in dynamic graph problems reveal promising connections to other areas which are still unexplored and only known among experts. The goal of the project is to deepen, broaden, and popularize the theory of these connections, and continue attacking fundamental barriers in the field, as they will likely lead to even more exciting tools and connections. This research direction goes hand-in-hand with educational plans, such as developing a new undergraduate course on the principles of dynamic algorithms, publishing online educational videos, and bringing together researchers from related areas to exchange ideas and techniques through workshops. More concretely, this project aims to investigate the following connections between dynamic graph algorithms and other areas. The first direction is to develop generic techniques for dynamic algorithms robust against an adaptive adversary by using connections to differential privacy, cryptography, and fine-grained complexity theory. The second direction is to develop new sublinear time algorithms, graph sparsification, and graph decomposition techniques that will lead to breakthroughs in dynamic algorithms. The third direction is to dynamize continuous optimization methods and develop optimization tools for dynamic problems. Via these connections, the investigator aims to obtain optimal algorithms for fundamental dynamic graph problems, including dynamic matching, max flow, and reachability problems. These are the holy-grail problems that have exponential upper and lower bound gaps. Hence, even partial progress should advance our understanding of the field and be useful as a subroutine for future algorithms. The multi-disciplinary approach above should naturally make impacts beyond dynamic graph algorithms. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.