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

点击翻译按钮获取中文摘要

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.