Research in Algorithms and Complexity

研究继续在几个应用领域，包括优化，人工智能，逻辑数据库，分布式决策，测试，并行计算和数学经济学，以及复杂性理论的基础上产生的计算问题的有效算法的发展。 该项目的重点是：（1）几个最优化问题的可逼近性，根据这一领域最近的重要进展;（2）沿着沿着三条线对在线算法进行竞争分析，使用竞争分析作为衡量分布式决策算法性能以及信息和通信价值的尺度;将该方法应用于由并行编译器驱动的问题;并试图解决K服务器猜想;（3）研究了与高效实现逻辑数据库查询有关的几个问题，以及进一步发展基于模型选择的快速非正式推理的计算理论;（4）研究严格介于P和NP之间的某些复杂性类，捕捉有限的非确定性和全函数;（5）在数理经济学中，将计算复杂性作为一种“科学隐喻”来捕捉有限理性;从算法的角度来看待博弈论和实现论中的一些关键问题;（6）研究与大型分布式系统测试相关的一些有趣的计算问题。

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.