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

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

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.