Perspectives on dynamic complexity theory

在过去的几十年里，从动态复杂性理论的角度对非常快速、并行、动态的算法进行了深入的探索。这样的算法是惊人的强大：其中，最近的研究表明，图的传递闭包可以在恒定的并行时间内动态保持。虽然在过去几年里，算法设计取得了重大进展，但对结构结果的关注要少得多。该项目的目标是系统地研究非常快速，并行，动态算法的复杂性理论问题。重点是探索(A)非常快速、并行、动态算法的能力障碍；(B)细粒度结构的小、并行动态复杂类；(C)动态并行计算模型与理论计算机科学其他领域之间的联系。

Very fast, parallel, dynamic algorithms have been intensely explored over the last decades from the perspective of dynamic complexity theory. Such algorithms are surprisingly powerful: among others, it was recently shown that the transitive closure of graphs can be maintained in constant parallel time dynamically. While there has been significant progress in algorithm design in the last years, a much lesser focus was on structural results. The goal of this project is a systematic study of complexity theoretic questions for very fast, parallel, dynamic algorithms. The focus is on exploring (A) barriers for the power of very fast, parallel, dynamic algorithms;(B) the fine-grained structure of small, parallel dynamic complexity classes; and(C) connections between dynamic parallel computational models and to other areas of theoretical computer science.