Parallel Algorithms and Complexity Theory

拟议研究的目标是了解并行计算的本质，为并行计算机系统的算法设计和分析发展理论基础，并应用这些原则来发现合适的并行计算机体系结构和算法。已经和正在进行研究的一些具体领域是：(1)针对各种自然问题的并行算法，(2)并行计算机模型及其相互关系，(3)并行机不能有效解决特定问题的下限或其他证据，以及(4)并行算法在现有处理器上的实现和测量。这是一位非常优秀的研究人员提出的一个很好的建议。提出的对并行计算的研究是目前计算机科学进步的基础。

The goals of the proposed research are to understand the nature of parallel computation, to develop theoretical foundations for the design and analysis of algorithms for parallel computer systems, and to apply these principles to discover appropriate parallel computer architectures and algorithms. Some of the specific areas in which research has been and is being conducted are: (1) parallel algorithms for a variety of natural problems, (2) models of parallel computers and their interrelationships, (3) lower bounds or other evidence that specific problems cannot be efficiently solved by parallel machines, and (4) implementation and measurement of parallel algorithms on currently available processors. This is an excellent proposal by a very fine researcher. The proposed study of parallel computing is fundamental for progress in computer science at this time.