Research

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:

  • 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.

Recent Papers

A complete list of my published work can be found here.

Preprints & In Submission
  • Space-Optimal Nearly-Local Forwarding on Trees (with Boaz Patt-Shamir). Submitted.
2018
  • On Sampling Edges Almost Uniformly (with Talya Eden). Symposium on Simplicity in Algorithms (SOSA) 2018. (DROPS, arXiv)

  • 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. (arXiv)

2017
  • The Space Requirement of Local Forwarding on Acyclic Networks (with Boaz Patt-Shamir). ACM Symposium on Principles of Distributed Computing (PODC), 2017. (ACM-DL)

  • Space-Time Tradeoffs for Distributed Verification (with Rafail Ostrovsky and Mor Perry). International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2017. (LNCS, arXiv)

2016
  • 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)
2015
  • Fast Distributed Almost Stable Matchings (with Rafail Ostrovsky). ACM Symposium on Principles of Distributed Computed (PODC), 2015. (ACM-DL, arXiv)

  • A Stable Marriage Requires Communication (with Yannai Gonczarowski, Noam Nisan, and Rafail Ostrovsky). ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015. (ACM-DL, arXiv)

  • 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)

Recent Talks

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)

  • The Space Requirement of Local Forwarding on Acyclic Networks, PODC 2017, Washington DC. (conference slides, seminar slides)

  • Space-time Tradeoffs for Distributed Verification, PODC 2016, Chicago, IL. (slides)

  • Stable Matchings with Bounded Preferences, Joint Math Meetings 2016, Seattle, WA. (slides)

  • The Stable Marriage Problem, Los Angeles Math Circle (High School II), 2016. (handout 1, handout 2)

  • 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.