CAREER: Theory for Dynamic Graph Algorithms

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

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.