Complexity Bounds in Parallel Computation

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

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.