CAREER: Theory for Dynamic Graph Algorithms

职业：动态图算法理论

• 批准号: 2238138
• 负责人: Thatchaphol Saranurak
• 金额: $ 65万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-09-01 至 2028-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2238138&HistoricalAwards=false
• 关键词: CAREER; Theory; 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.

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