It is a common theme in algorithm design—as in everyday life—that we must make decisions based on incomplete, inaccurate, or ambiguous information. Uncertainty may arise as a result of locality (relevant information is located far away), congestion (data can only be moved at a fixed rate), variability in the outcomes of concurrent and future events, or the behavior of noisy, self-interested, or malicious elements. Even if information can be obtained reliably, there may simply be too much data to disseminate before we must make a decision.
The central theme of my research is to understand the algorithmic cost of uncertainty. I address issues of uncertainty formally through the lenses of distributed computing and computational complexity. Most of the problems I study can be formalized in the language of graph theory, and much of my work focuses on understanding the role of communication in solving problems on graphs. In particular, some recent topics I have worked on include:
- Clock Synchronization
- Adversarial Queueing Theory
- Distributed and Sublinear Time Graph Algorithms
- Distributed Verification and Proof Labeling Schemes
- The Stable Marriage Problem