The Complexity of Parallel Computations

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

This research project focuses on parallel computation. Its aim is to advance the basic understanding of parallel computers. The primary goals are to develop new techniques to solve problems efficiently in parallel, to produce new parallel approximation algorithms, to determine why some problems do not parallelize well, and to address the parallel complexity of some fundamental open problems. Problems from three general areas: algebra, geometry, and graph theory will be studied.