Parallel Algorithms and Complexity Theory

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

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.