U.S.-Germany Cooperative Research on Structure in ComplexityTheory

该奖项分别支持罗切斯特大学的Lane教授和勒莫恩学院的Edith Hemaspaandra教授与德国耶拿弗里德里希·席勒大学的Gerd Wechsung教授在计算机科学方面的合作。他们将共同研究计算复杂性理论中当前感兴趣的几个主题，其中包括(1)对查询顺序对复杂性的影响的严格研究（即，访问多个信息源的顺序是否以及何时重要）和(2)证书复杂性（计算控制集合类大小的条件，这些集合总是具有易于计算的接受证书）。参与这项合作的美国和德国在创造性理论方面和计算复杂性的严格数学方面发挥了互补的优势。这些天才和多产的研究人员的共同努力将对复杂性理论的结构方面的研究作出重大贡献。结果将在计算机和信息科学的许多方面产生影响。

This award supports Professors Lane and Edith Hemaspaandra, of the University of Rochester and Le Moyne College, respectively, to collaborate in computer science with Professor Gerd Wechsung of the Friedrich Schiller University of Jena, Germany. Together they will study several topics of current interest in computational complexity theory These include (1) rigorous studies of the effect of query order on complexity (i.e., whether and when the order of access to multiple information sources matters) and (2) certificate complexity (calculating the conditions that control the size of classes of sets which always have acceptance certificates that can be easily computed.) The U.S. and German participants in this collaboration bring to bear complementary strengths in the creative theoretical aspects and the rigorous mathematical aspects of computational complexity. The joint effort of these talented and prolific researchers should produce significant contributions to the study of structural aspects of complexity theory. Results will have implications in many aspects of computer and information science.