Grant: Discovery Grants Program - Individual

Complexity and parallel algorithms Parallel complexity theory studies the algorithms, machine structures, networks, and resources needed for parallel computing (including parallel time, communication costs and number of processors.) Many computational tasks remain beyond the reach of even the fastest sequential processors. The long-term objective of this research is the development of a general theory of methods to solve computational tasks efficiently on massively parallel and/or widely distributed processors. To make progress on this objective, many significant problems must be addressed, including learning how algorithms can be designed to make effective use of parallelism (i.e. efficiently make use of many processors). In addition, we study application areas of parallel and distributed computing, including multi-agent robotics and path planning, with applications to robot search and to accessibility assessment.