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
- 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.
A complete list of my published work can be found here.
Preprints & In Submission
The Arboricity Captures the Complexity of Sampling Edges (with Talya Eden and Dana Ron). (arXiv)
With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing (with Avery Miller and Boaz Patt-Shamir). (arXiv)
Fault Tolerant Gradient Clock Synchronization (with Johannes Bund and Christoph Lenzen). (arXiv)
- Space-Optimal Nearly-Local Forwarding on Trees (with Boaz Patt-Shamir). IEEE International Conference on Computer Communications (INFOCOM) 2019.
Lower Bounds for Approximating Graph Parameters via Communication Complexity (with Talya Eden). The 21st International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2018. (DROPS, arXiv)
The Space Requirement of Local Forwarding on Acyclic Networks (with Boaz Patt-Shamir). ACM Symposium on Principles of Distributed Computing (PODC), 2017. (ACM-DL)
- Brief Announcement: Space-Time Tradeoffs for Distributed Verification (with Mor Baruch and Rafail Ostrovsky). ACM Symposium on Principles of Distributed Computing (PODC), 2016. (ACM-DL)
It’s Not Easy Being Three: The Approximability of Three-Dimensional Stable Matching Problems (with Rafail Ostrovsky). International Workshop on Matching Under Preferences (MATCH-UP), 2015. (arXiv)
A complete list of talks can be found here.
On Sampling Eges Almost Uniformly, Symposium on Simplicity in Algorithms (SOSA) 2018, New Orleans, LA. (slides)
Space-time Tradeoffs for Distributed Verification, PODC 2016, Chicago, IL. (slides)
Stable Matchings with Bounded Preferences, Joint Math Meetings 2016, Seattle, WA. (slides)
Fast Distributed Almost Stable Matchings, PODC 2015, San Sebastien, Spain. (slides)
It’s Not Easy Being Three: The Approximability of Three-Dimensional Stable Matching Problems MATCH-UP 2015, Glasgow, Scotland, UK. (slides)
A Stable Marriage Requires Communication. Mathematics Department Colloquium, Reed College, Spring 2015.