Designing algorithms for dynamic data

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

Many of the computational problems we are interested in are formulated in terms of a fixed input. They are problems of the form ``given some input x, what is the value of some function f on this input x''; the function f being the computational problem we are trying to solve, and our task being to design an (efficient) algorithm that can compute this function. Given some computational problem f, it is natural to ask how the output of f changes as we modify the input to f, i.e. given some input x, if we make some small modification to x in order to obtain some x + \Delta, how will f(x) be related to f(x + \Delta)? Can we use f(x) to compute f(x+\Delta) more efficiently than just computing the value of f on this new input from scratch? In the dynamic setting, instead of computing a solution to f on some fixed input x, we are interested in maintaining a solution to f on some input x which changes as we perform updates via a sequence of insertions and deletions. In this setting, our task is to design an algorithm that can efficiently update the solution of the problem after we perform some update to the input. The time taken to update the solution after the insertion/deletion is referred to as the update time. Two related setting are the incremental setting, where we only allow insertions to the data specifying the input, and the decremental setting, where we only allow deletions. As our ability to gather and store data continues to grow, the importance of more advanced algorithms which are capable to processing and maintaining data sets more efficiently has become apparent. This clear practical motivation for the development of dynamic algorithms has led to this area becoming a vibrant and very important area of research within theoretical computer science, and there have been many fascinating developments within the area over the past decades, with much of the interest stemming from results showing that important and well studied problems in the static setting admit dynamic algorithms with polylogarithmic update times in the fully dynamic setting. However, even some of the simplest and most fundamental problems in computer science still remain elusive problems in the dynamic setting, and are far from being fully understood. One such problem is that of cycle detection in directed graphs, where there is still a large gap between the static and dynamic settings, where the optimal solution in the static setting is a well known textbook problem and is commonly taught in introductory algorithms courses, while the best known algorithms for the problem, even just in the incremental setting, are highly non-trivial and still far from what many believe to be optimal. This disparity between the static and dynamic settings makes research in dynamic algorithms a fascinating endeavour with many well motivated open problems on the horizon. The main goal of this project will be to tackle important open problems in this area and make progress in answering fundamental questions in dynamic algorithms.