DIMACS Special Year 1990-91 on Complexity Theory of Interactive Computation


DIMACS' second special year began on September 1, 1990 and ended on August 31, 1991. The theme of the special year was complexity theory of interactive computation. It was concerned with the theory of computation involving more that one participant.

The subject of computing with distributed participants has arisen in many different forms in the past ten years. This was the first time that a large-scale endeavor was launched to bring together a substantial group of researchers in this area, researchers who normally worked in differend subfields, but share a common set of mathematical tools in complexity theory and number theory. There were five workshops held during the year, on the topics cryptography; structural complexity and cryptography; circuit and communication complexity; computational number theory; and learning theory. The five workshops not only provided a forum for researchers to present the most recent results in their subfields, but they also fostered many cross-field interactions which otherwise might not have occurred. For example, the lectures on new ideas for factoring integers, given by Lenstra and Schnoor during the cryptography workshops, were much appreciated by the computer science audience, most of whom had not kept abreast of this subject of great importance to cryptography.


Up. Index of DIMACS Special Year on Complexity Theory of Interactive Computation
DIMACS Homepage
Contacting the Center
Document last modified on October 19, 1998.