Studies in Concrete Complexity

该项目涉及算法和计算复杂性理论中的三个问题领域，其目标是增加对解决特定问题的各种计算模型的能力和局限性的了解。(1)第一部分旨在推导电路计算布尔函数的计算难度的下界。(2)第二部分涉及在线计算问题的分析，即输入作为请求序列提供的问题，并且必须在接收序列时产生输出响应，而不是在所有请求都已知之后。在特定情况下，目标是开发一种算法，其性能优于该问题的最佳离线算法。工作的重点是开发用于分析在线问题结构的工具，并使用该结构来确定在线算法可能有多好。(3)第三部分考虑了分布式计算中的问题。我们的目标是理解协调一组松散连接的处理器时的两个基本问题：在这样一个系统中，处理器之间可以达成什么样的协议，以及如何有效地执行资源调度。

This project addresses three problem areas in the theory of algorithms and computational complexity, with the goal to increase knowledge about the power and limitations of various computational models for solving specific problems. (1) The first part aims at deriving lower bounds for the computational difficulty of computing Boolean functions by circuits. (2) The second part deals with the analysis of on-line computational problems, that is, problems where the input is provided as a sequence of requests and an output response must be produced as the sequence is being received rather than after all requests are known. The aim in a particular situation is to develop an algorithm whose performance compares favorably with the best off-line algorithm for the problem. The focus of the work is to develop tools for analyzing the structure of on-line problems and to use the structure to determine how good an on-line algorithm is possible. (3) In the third part, problems in distributed computing are considered. The goal is to develop an understanding of two basic issues in coordinating a set of loosely linked processors: what kind of agreement can be reached among processors in such a system, and how can resource scheduling be efficiently performed.