research

overview

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

Here are links to my Google Scholar profile and DBLP page.

recent talks

• Buffer Space and Locality in Packet Forwarding Aalto University, August 2023 slides
• Packet Forwarding with a Locally Bursty Adversary DISC 2022, October 2022 slides
• Bias Reduction for Sum Estimation FODSI Sublinear Algorithms Workshop at MIT, August 2022 slides
• Sampling Edges and More UMass CS Theory Seminar, February 2021 slides
• Stable Matchings with Restricted Preferences, EC 2021 slides (very short version)
• The Space Requirement of Local Forwarding on Acyclic Networks, PODC 2017 slides