Parallelism, Communication and Randomness in Models of Computation, and Efficient Computation in Permutation Groups

人们正在研究根据各种模型进行的计算的基本特征的力量。pi和其他人最近在通信复杂性理论和图灵复杂性中定义了新的类。在这些新类中，Arthur-Merlin协议定义的类是交互式证明系统的近亲。在这些新职业中，互动性和随机性都扮演着重要角色。这些新类别的分离特性正在研究中。特别令人感兴趣的是通信复杂性理论中多项式时间层次的分离问题，以及Arthur-Merlin协议决定的语言类与近np语言类的关系。pi也在继续研究异步分布式网络中的可靠性问题。pi最近完成了排列群隶属性属于NC类的证明。他们的方法似乎对顺序情况有影响，他们正在探索获得顺序情况的实质性加速的可能性。相互作用和随机性在计算中的作用是理论界目前最感兴趣的问题。在发展对这些角色的理解方面，pi是领军人物。

Research is being conducted into the power of fundamental features of computation carried out according to various models. The PIs and others have recently defined new classes in communication complexity theory and also in Turing Complexity. Among such new classes are those defined by Arthur-Merlin protocols which are close relatives of interactive proof systems. Both interaction and randomness play important roles in most of these new classes. Separation properties for these new classes are being studied. Of particular interest are the separation problem of the polynomial time hierarchy in communication complexity theory and the relation of the class of languages determined by Arthur-Merlin protocols to the class of almost-NP languages. The PIs are also continuing their investigation of reliability problems in asynchronous distributed networks. The PIs have recently completed the proof that permutation group membership is in the class NC. Their methods appear to have implications for the sequential case and they are exploring the possibility of obtaining a substantial speedup for the sequential situation. The roles of interaction and randomness in computation are of crucial interest to the theory community at this time. The PIs are leading figures in the development of the understanding of these roles.