Power and Limitations of Conceptually Simple Algorithms

理论计算机科学在设计新的高效和实用的算法以及分析和解释现有算法的性能方面都取得了巨大的成功。然而，“理论”和“实践”之间的差距依然存在。最常见的批评之一是，最坏情况分析往往过于悲观，无法反映出“实践”。这种现象的主要例子是线性规划和可满足性问题。另一种批评是，负面结果往往建立在假设的基础上。有时这些假设是相当合理的，如P不等于NP，但有时这些假设更具争议性，如强指数时间假设。还有另一个批评是，计算模型可能缺乏一些实用功能，例如，算法可能可用的额外辅助信息。边际信息在理论上通常是由一个全能的先知来建模的，在这个模型中，“全能”的部分是不太现实的。虽然没有单一的“灵丹妙药”模式可以解决所有这些问题，但在试图将实践与理论联系起来的尝试中，有许多成功的案例。这项研究计划属于这种试图缩小理论和实践之间的差距的保护伞，因为它属于概念上简单的算法。从概念上来说，简单的算法有许多属性，这些属性使它们在实践中变得可取，但它们很难分析。问题的一部分是，通常简单的算法有糟糕的最坏情况行为，但经验性能很好。符合这种现实的分析必须准确地模拟实际情况，这已经是一项非常困难的任务。另一个问题是，简单性的概念没有得到很好的定义。这使得对以下形式的问题的回答是否定的：“这个问题能用简单的算法解决吗？”不可能。这个项目的长期目标是开发一种简单算法的正式理论，以解决上述三个批评。短期目标包括实用的输入建模、带有信息论瓶颈的算法建模，以及针对不同应用领域中的特定问题(如在线广告、调度、打包和优化)评估概念性简单的算法。

Theoretical computer science has been hugely successful in terms of both design of new efficient and practical algorithms, as well as analysis and explanation of performance of existing algorithms. Yet, the gap between "theory" and "practice" remains. One of the most common criticisms is that worst-case analysis is often too pessimistic to reflect "practice". Prime examples of this phenomenon are linear programming and satisfiability problems. Another criticism is that negative results are often based on assumptions. Sometimes these assumptions are quite reasonable, such as P not equal to NP, but other times these assumptions are more controversial, such as strong exponential time hypothesis. Yet another criticism is that computational models might lack some practical features, e.g., extra side information that might be available to an algorithm. Side-information is often modelled in theory by an all-powerful oracle, where the "all-powerful" part is not very realistic. While there is no single "silver bullet" model that addresses all these concerns, there are many success stories in attempts to bridge practice and theory. This research program falls under this umbrella of trying to reduce the gap between theory and practice as it pertains to conceptually simple algorithms. Conceptually simple algorithms have many properties that make them desirable in practice, but they are hard to analyze. Part of the problem is that usually simple algorithms have bad worst-case behavior, but excellent empirical performance. An analysis consistent with such reality has to accurately model practical instances, which already is a very difficult task. Another problem is that the notion of simplicity is not well-defined. This makes negative answers to questions of the form "can this problem be solved by a simple algorithm?" impossible. The long-term goal of this project is to develop a formal theory of simple algorithms that would address the three criticisms mentioned above. Short-term goals consist of practical input modelling, algorithmic modelling with information-theoretic bottlenecks, and evaluation of conceptually simple algorithms for specific problems within various application domains, such as online advertising, scheduling, packing, and optimization.