Design and Analysis of Algorithms

Description

We study applications of probability theory to the design and analysis of algorithms. Randomness comes up in two aspects of the study of algorithms: randomized algorithms and probabilistic analysis of algorithms. In randomized algorithms, we are particularly interested in algorithms for communication and distributed applications, as well as online combinatorial problems. In probabilistic analysis, our work focuses on the long-term steady-state performance of dynamic processes.

We also study combinatorial algorithms, which treat computations on finite, discrete mathematical structures. Topics include searching, sorting, and enumeration, data structures, graph algorithms, external-memory algorithms, combinatorial optimization, approximation algorithms for NP-hard problems, online algorithms, and algorithm engineering.