Complexity Bounds in Parallel Computation

通过Barrington、Razborov和Smolensky等研究者的工作，最近出现了一种新的并行复杂性代数方法。在这样的工作中，使用有限置换群和多项式环在素阶域上，其中的不定式被假定为幂等的。pi正在通过分析这些相关的代数结构来研究并行计算的复杂性。他们还开发了一种新的计算模型，他们称之为“安全存储机器”，这种机器会周期性地丢失除一定数量的内存外的所有内存。正在进行的是语言类的特征描述，以及通过这种新模型的变体可以定义的谓词。理论计算机科学界对并行计算中新发展的代数问题的探索非常感兴趣。pi为这项研究带来了广泛而强大的集体背景。

A new algebraic approach to parallel complexity has recently been emerging through the work of such investigators as Barrington, Razborov, and Smolensky. In such work use is made of finite permutation groups and also of rings of polynomials over fields of prime order for which the indeterminants are assumed to be idempotent. The PIs are investigating the complexity of parallel computation through the analysis of such associated algebraic structures. They have also developed a new model of computation that they call the "safe storage machine" which periodically loses all but a constant amount of its memory. In progress are characterizations of classes of languages and predicates definable by means of variations of this new model. There is much interest in the theoretical computer science community in the exploration of the newly developed algebraic view of questions in parallel computation. The PIs bring a broad strong collective background to this study.