Focus Areas: Theory
My main research area is computational complexity — estimating the amount of resources (such as memory, time, number of algebraic operations, or interprocess communication) that are needed to compute functions. One tries to get good upper bounds by exhibiting efficient algorithms and to develop mathematical methods to prove lower bounds. I am especially interested in lower bound techniques for parallel and for probabilistic models. I am also interested in dstributed computing, especially in fault tolerant distributed computations.
Labs & Groups
Theoretical Computer Science Group
The Theory group plays a fundamental role in connecting CS with physics, statistics, and other mathematical sciences.