RIA: On-Line and Dynamic Algorithms: Computing with an Uncertain Future

该项目涉及在线和动态算法的研究-算法类型的统一主题是未来对算法请求的不确定性。从信息论和数据压缩（特别是随机复杂性）的经验中，引入了平均情况分析的新方法来研究在线算法。此外，研究了当输入请求来自已知分布时，在线最优决策的计算复杂度。在动态算法和数据结构领域，通过检查现有（或可能是新的）并行算法的结构，开发了设计动态算法的技术。最初的结果显示了如何使用代数电路易于计算的性质来设计动态算法，这些结果在本项目中被扩展到涉及更复杂的输入增量操作的更广泛的问题。此外，开发了并行机的动态算法，这对于需要对动态变化的数据进行快速响应的应用非常重要。

This project involves the study of both on-line and dynamic algorithms---types of algorithms with the unifying theme of uncertainty about future requests to the algorithm. New methods of average-case analysis are introduce to the study of on-line algorithms, drawing from experience in information theory and data compression (and, in particular, from stochastic complexity). In addition, the computational complexity of making optimal on-line decisions when the input requests are drawn from a known distribution, is investigated. In the area of dynamic algorithms and data structures, techniques are developed for designing dynamic algorithms by examining the structure of existing (or perhaps new) parallel algorithms. Initial results show how to use easily computable properties of algebraic circuits in order to design dynamic algorithms, and these results are extended in this project to a wider class of problems involving more complex incremental operations on the inputs. In addition, dynamic algorithms for parallel machines are developed, which are important for applications which require very fast response to dynamically changing data.