Foundations of work-efficient constant-time parallel dynamic and static algorithms

该项目旨在从工作效率的角度扩展动态复杂性理论的研究，从而为丰富动态算法的研究领域搭建一座桥梁。最近在动态复杂性理论的研究中发现了许多算法问题，这些问题可以用并行随机存取模型(PRAM)上的动态并行算法来维持，而与输入的大小无关，只需恒定的时间。作为一个例子，证明了有向图的可达性问题可以在边插入和边删除的情况下被这样的算法维持。然而，这项研究只关注恒定时间方面，而忽略了效率的其他方面，最显著的是工作，即所有处理器上的总步数。因此，文献中的算法所需的工作量严重阻碍了它们的实际应用。这个项目的主要目标是为重要的算法问题设计工作效率高的恒定时间并行动态算法，并开发通用的算法技术。一个密切相关的额外目标是设计工作效率高的恒定时间并行静态算法，特别是对子任务的动态算法。互补性调查将试图找出这两种算法存在和工作效率的障碍，并设计一种可以指定这种动态算法的语言。

The project aims to extend the research in Dynamic Complexity Theory by the aspect of work-efficiency and thus build a bridge to the rich research area of Dynamic Algorithms. Recent research in Dynamic Complexity Theory has identified many algorithmic problems that can be maintained by dynamic parallel algorithms with only constant time on the Parallel Random Access Model (PRAM), independent of the size of inputs. As an example, it has been shown that the reachability problem for directed graphs can be maintained by such algorithms under edge insertions and edge deletions. However, this research has focussed solely on the constant-time aspect and has ignored other aspects of efficiency, most notably the work, i.e. the overall number of steps summed over all processors. As a result, the amount of work needed by the algorithms in the literature is a serious obstacle to their practical usefulness. The main goal of this project is to design work-efficient constant-time parallel dynamic algorithms for important algorithmic problems and to develop versatile algorithmic techniques. A closely related additional goal is to design work-efficient constant-time parallel static algorithms, in particular for sub-tasks of dynamic algorithms. Complementary investigations will try to identify barriers for the existence and work-efficieny of both kinds of algorithms and to design a language by which such dynamic algorithms can be specified.