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.