Designing algorithms for dynamic data

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

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.