Designing algorithms for dynamic data

我们感兴趣的许多计算问题都是根据固定输入来表述的。它们是这样的问题“给定某个输入x，某个函数f在这个输入x上的值是多少”函数f是我们试图解决的计算问题，我们的任务是设计一个（有效的）算法来计算这个函数。给定某个计算问题f，很自然地会问，当我们修改f的输入时，f的输出是如何变化的，也就是说，给定某个输入x，如果我们对x做一些小的修改以获得某个x + \Delta，那么f(x)与f（x + \Delta）有什么关系？我们是否可以用f(x)来计算f（x+\）比在这个新输入上从头开始计算f的值更有效？在动态设置中，我们感兴趣的不是计算某个固定输入x上f的解，而是维护某个输入x上f的解，当我们通过一系列插入和删除执行更新时，这个输入x会发生变化。在这种情况下，我们的任务是设计一个算法，在我们对输入执行一些更新后，可以有效地更新问题的解决方案。在插入/删除之后更新解决方案所花费的时间称为更新时间。两个相关的设置是增量设置，我们只允许插入指定输入的数据，以及递减设置，我们只允许删除。随着我们收集和存储数据的能力不断增长，能够更有效地处理和维护数据集的更先进算法的重要性已经变得明显。动态算法发展的这种明确的实际动机使该领域成为理论计算机科学中一个充满活力和非常重要的研究领域，在过去的几十年里，该领域取得了许多令人着迷的发展，其中许多兴趣源于结果表明，在静态设置中重要且研究得很好的问题允许在完全动态设置中具有多对数更新时间的动态算法。然而，即使是计算机科学中一些最简单和最基本的问题，在动态环境中仍然是难以捉摸的问题，远远没有被完全理解。其中一个问题是有向图中的循环检测，静态和动态设置之间仍然存在很大的差距，静态设置中的最优解是众所周知的教科书问题，通常在入门算法课程中教授，而该问题的最知名算法，甚至只是在增量设置中，都是高度非平凡的，仍然远离许多人认为的最优解。静态和动态设置之间的这种差异使得动态算法的研究成为一项引人入胜的努力，许多动机良好的开放问题即将出现。该项目的主要目标是解决该领域的重要开放问题，并在回答动态算法中的基本问题方面取得进展。

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.