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.