Studies in Concrete Complexity

点击翻译按钮获取中文摘要

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.