CAREER: Theory for Dynamic Graph Algorithms

图表是数据之间关系最自然的表现形式之一，因此，几乎在每个科学分支中都有使用。不幸的是，传统的图形算法往往不再可行，因为图形在现代应用程序中，如互联网/流量/社交网络，总是在不断发展。为了解决这个问题，动态图算法研究旨在设计有效的方法来维护图上的有用信息（例如，连通性，最短路径，匹配），而不是在每次更新后重新计算答案。在过去的几年里，动态图问题的几个突破揭示了与其他尚未探索和只有专家知道的领域的有希望的联系。该项目的目标是深化、拓宽和普及这些连接的理论，并继续突破该领域的基本障碍，因为它们可能会带来更令人兴奋的工具和连接。这一研究方向与教育计划密切相关，例如开发一门关于动态算法原理的新本科课程，发布在线教育视频，以及通过研讨会将相关领域的研究人员聚集在一起交流思想和技术。更具体地说，该项目旨在研究动态图算法与其他领域之间的以下联系。第一个方向是开发动态算法的通用技术，通过使用与差分隐私、密码学和细粒度复杂性理论的联系来抵御自适应对手。第二个方向是开发新的次线性时间算法、图稀疏化和图分解技术，这些技术将导致动态算法的突破。第三个方向是动态化连续优化方法，开发针对动态问题的优化工具。通过这些联系，研究者的目标是获得基本动态图问题的最佳算法，包括动态匹配，最大流量和可达性问题。这些都是具有指数上界和下界间隙的圣杯问题。因此，即使是部分进展也应该促进我们对该领域的理解，并作为未来算法的子程序有用。上述多学科方法自然会产生超越动态图算法的影响。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.