Perspectives on dynamic complexity theory

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

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.