Research in Algorithms and Complexity

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

Research continues on the development of efficient algorithms for computational problems arising in several application areas, including Optimization, Artificial Intelligence, Logic Databases, Distributed Decision-Making, Testing, Parallel Computation, and Mathematical Economics, as well as on the foundations of Complexity Theory. This project focuses on: (1) the approximability of several optimization problems, in the light of recent important advances in this area; (2) work on the competitive analysis of on-line algorithms along three lines, using competitive analysis as a yardstick for measuring the performance of distributed decision-making algorithms, as well as the value of information and communication; applying the methodology to problems motivated by parallel compilers; and trying to resolve the K-server conjecture; (3) work on several problems related to the efficient implementation of logic database queries, as well as in further developing a computational theory of rapid informal reasoning based on model selection; (4) the study of certain complexity classes that appear to lie strictly between P and NP, capturing limited non determinism and total functions; (5) the use of computational complexity as a `scientific metaphor` for capturing bounded rationality in Mathematical Economics; looking from the algorithmic point of view at some key problems in the Theory of Games and that of Implementation; and (6) work on some interesting computational problems related to testing large distributed systems.