PYI: Complexity of Parallel Algorithms

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

The PI is studying the complexity of parallel algorithms. One direction of the research is to develop fast parallel algorithms for simple combinatorial problems using an idealized model of parallel computation. The major issue is to identify techniques that yield algorithms that are both fast and make an efficient use of processors. A second direction of research is to study realistic models of parallel computation. There is currently a large gap between the theoretical models of parallel computation and feasible parallel machines. An attempt is being made to close this gap by studying models that incorporate features such as locality of reference, memory contention and varying degrees of synchronization. The PI has been judged to be an outstanding computer scientist by the Presidential Young Investigator panel.