publications

2022

1. Stable Matchings with Restricted Preferences: Structure and Complexity

   Christine T. Cheng, and Will Rosenbaum

   ACM Transactions on Economics and Computataion 2022

   Abs arXiv HTML

   In the stable marriage (SM) problem, there are two sets of agents—traditionally referred to as men and women—and each agent has a preference list that ranks (a subset of) agents of the opposite sex. The goal is to find a matching between men and women that is stable in the sense that no man-woman pair mutually prefer each other to their assigned partners. In a seminal work, Gale and Shapley [16] showed that stable matchings always exist, and described an efficient algorithm for finding one. Irving and Leather [24] defined the rotation poset of an SM instance and showed that it determines the structure of the set of stable matchings of the instance. They further showed that every finite poset can be realized as the rotation poset of some SM instance. Consequently, many problems—such as counting stable matchings and finding certain “fair” stable matchings—are computationally intractable (NP-hard) in general. In this paper, we consider SM instances in which certain restrictions are placed on the preference lists. We show that three natural preference models—k-bounded, k-attribute, and (k1, k2)-list—can realize arbitrary rotation posets for constant values of k. Hence even in these highly restricted preference models, many stable matching problems remain intractable. In contrast, we show that for any fixed constant k, the rotation posets of k-range instances are highly restricted. As a consequence, we show that exactly counting and uniformly sampling stable matchings, finding median, sex-equal, and balanced stable matchings are fixed-parameter tractable when parameterized by the range of the instance. Thus, these problems can be solved in polynomial time on instances of the k-range model for any fixed constant k.

2. Packet Forwarding with a Locally Bursty Adversary

   Will Rosenbaum

   In 36th International Symposium on Distributed Computing (DISC 2022) 2022

   Abs arXiv HTML

   We consider packet forwarding in the adversarial queueing theory (AQT) model introduced by Borodin et al. We introduce a refinement of the AQT (ρ, σ)-bounded adversary, which we call a locally bursty adversary (LBA) that parameterizes injection patterns jointly by edge utilization and packet origin. For constant (O(1)) parameters, the LBA model is strictly more permissive than the (ρ, σ) model. For example, there are injection patterns in the LBA model with constant parameters that can only be realized as (ρ, σ)-bounded injection patterns with ρ+ σ= Ω(n) (where n is the network size). We show that the LBA model (unlike the (ρ, σ) model) is closed under packet bundling and discretization operations. Thus, the LBA model allows one to reduce the study of general (uniform) capacity networks and inhomogenous packet sizes to unit capacity networks with homogeneous packets. On the algorithmic side, we focus on information gathering networks—i.e., networks in which all packets share a common destination, and the union of packet routes forms a tree. We show that the Odd-Even Downhill (OED) forwarding protocol described independently by Dobrev et al. and Patt-Shamir and Rosenbaum achieves buffer space usage of O(\log n) against all LBAs with constant parameters. OED is a local protocol, but we show that the upper bound is tight even when compared to centralized protocols. Our lower bound for the LBA model is in contrast to the (ρ, σ)-model, where centralized protocols can achieve worst-case buffer space usage O(1) for ρ, σ= O(1), while the O(\log n) upper bound for OED is optimal only for local protocols.

3. Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques in Bounded Arboricity Graphs

   Talya Eden, Dana Ron, and Will Rosenbaum

   In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 2022

   Abs arXiv HTML

   Counting and sampling small subgraphs are fundamental algorithmic tasks. Motivated by the need to handle massive datasets efficiently, recent theoretical work has examined the problems in the sublinear time regime. In this work, we consider the problem of sampling a k-clique in a graph from an almost uniform distribution. Specifically the algorithm should output each k-clique with probability (1 \pm ε)/n_k, where n_k denotes the number of k-cliques in the graph and εis a given approximation parameter. To this end, the algorithm may perform degree, neighbor, and pair queries. We focus on the class of graphs with arboricity at most α, and prove that the query complexity of the problem is \[ Θ^*\left(\min\left( nα, \max\left(\left((nα)^ k/2 / n_k\right)^1/(k-1), (nα^k-1)/n_k \right)\right)\right), \]where n is the number of vertices in the graph, and Θ^*(⋅) suppresses dependencies on (\log n/ε)^O(k). Our upper bound is based on defining a special auxiliary graph H_k, such that sampling edges almost uniformly in H_k translates to sampling k-cliques almost uniformly in the original graph G. We then build on a known edge-sampling algorithm (Eden, Ron and Rosenbaum, ICALP19) to sample edges in H_k. The challenge is simulating queries to H_k while being given query access only to G. Our lower bound follows from a construction of a family of graphs with arboricity αsuch that in each graph there are n_k k-cliques, where one of these cliques is “hidden” and hence hard to sample.

2021

1. Stable Matchings with Restricted Preferences: Structure and Complexity

   Christine T. Cheng, and Will Rosenbaum

   In EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021 2021

   Abs arXiv HTML

   It is well known that every stable matching instance I has a rotation poset R(I) that can be computed efficiently and the downsets of R(I) are in one-to-one correspondence with the stable matchings of I. Furthermore, for every poset P, an instance I(P) can be constructed efficiently so that the rotation poset of I(P) is isomorphic to P. In this case, we say that I(P) realizes P. Many researchers exploit the rotation poset of an instance to develop fast algorithms or to establish the hardness of stable matching problems. In order to gain a parameterized understanding of the complexity of sampling stable matchings, Bhatnagar et al. [SODA 2008] introduced stable matching instances whose preference lists are restricted but nevertheless model situations that arise in practice. In this paper, we study four such parameterized restrictions; our goal is to characterize the rotation posets that arise from these models: k-bounded, k-attribute, (k_1, k_2)-list, k-range. We prove that there is a constant k so that every rotation poset is realized by some instance in the first three models for some fixed constant k. We describe efficient algorithms for constructing such instances given the Hasse diagram of a poset. As a consequence, the fundamental problem of counting stable matchings remains #BIS-complete even for these restricted instances. For k-range preferences, we show that a poset P is realizable if and only if the Hasse diagram of P has pathwidth bounded by functions of k. Using this characterization, we show that the following problems are fixed parameter tractable when parametrized by the range of the instance: exactly counting and uniformly sampling stable matchings, finding median, sex-equal, and balanced stable matchings.

2020

1. PALS: Plesiochronous and Locally Synchronous Systems

   Johannes Bund, Matthias Függer, Christoph Lenzen, Moti Medina, and Will Rosenbaum

   In 26th IEEE International Symposium on Asynchronous Circuits and Systems, ASYNC 2020, Salt Lake City, UT, USA, May 17-20, 2020 2020

   Abs arXiv HTML

   Consider an arbitrary network of communicating modules on a chip, each requiring a local signal telling it when to execute a computational step. There are three common solutions to generating such a local clock signal: (i) by deriving it from a single, central clock source, (ii) by local, free-running oscillators, or (iii) by handshaking between neighboring modules. Conceptually, each of these solutions is the result of a perceived dichotomy in which (sub)systems are either clocked or fully asynchronous, suggesting that the designer’s choice is limited to deciding where to draw the line between synchronous and asynchronous design. In contrast, we take the view that the better question to ask is how synchronous the system can and should be. Based on a distributed clock synchronization algorithm, we present a novel design providing modules with local clocks whose frequency bounds are almost as good as those of corresponding free-running oscillators, yet neighboring modules are guaranteed to have a phase offset substantially smaller than one clock cycle. Concretely, parameters obtained from a 15nm ASIC implementation running at 2GHz yield mathematical worst-case bounds of 30ps on phase offset for a 32x32 node grid network.

2. Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems

   Will Rosenbaum, and Jukka Suomela

   In PODC ’20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020 2020

   Abs arXiv HTML

   Consider a graph problem that is locally checkable but not locally solvable: given a solution we can check that it is feasible by verifying all constant-radius neighborhoods, but to find a solution each node needs to explore the input graph at least up to distance Ω(\log n) in order to produce its output. We consider the complexity of such problems from the perspective of volume: how large a subgraph does a node need to see in order to produce its output. We study locally checkable graph problems on bounded-degree graphs. We give a number of constructions that exhibit tradeoffs between deterministic distance, randomized distance, deterministic volume, and randomized volume: (1) If the deterministic distance is linear, it is also known that randomized distance is near-linear. In contrast, we show that there are problems with linear deterministic volume but only logarithmic randomized volume. (2) We prove a volume hierarchy theorem for randomized complexity: among problems with linear deterministic volume complexity, there are infinitely many distinct randomized volume complexity classes between Ω(\log n) and O(n). This hierarchy persists even when restricting to problems whose randomized and deterministic distance complexities are Θ(\log n). (3) Similar hierarchies exist for polynomial distance complexities: for any k, \ell ∈N with k ≤\ell, there are problems whose randomized and deterministic distance complexities are Θ(n^1/\ell), randomized volume complexities are Θ(n^1/k), and whose deterministic volume complexities are Θ(n). Additionally, we consider connections between our volume model and massively parallel computation (MPC). We give a general simulation argument that any volume-efficient algorithm can be transformed into a space-efficient MPC algorithm.

2019

1. A stable marriage requires communication

   Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, and Will Rosenbaum

   Games and Economic Behavior 2019

   Abs arXiv HTML

   In 1976, Knuth asked whether the worst-case running-time of the Gale-Shapley algorithm for the Stable Marriage Problem can be improved when non-sequential access to the input is allowed. Partial negative answers were given by Ng and Hirschberg and as part of Segal’s general communication-complexity analysis. We give a far simpler, yet significantly more powerful, argument showing that Ω(n^2) Boolean queries of any type are required for finding a stable — or even approximately stable — marriage. Unlike Segal’s lower bound, our lower bound generalizes additionally to (A) randomized algorithms, (B) allowing arbitrary separate preprocessing of the women’s and men’s respective preferences profiles, (C) related problems, e.g., whether a given pair is married in every/some stable marriage, (D) whether a proposed marriage is stable or far from stable. To analyze “approximately stable” marriages, we introduce the notion of “distance to stability” and provide an efficient algorithm for its computation.

2. The Arboricity Captures the Complexity of Sampling Edges

   Talya Eden, Dana Ron, and Will Rosenbaum

   In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece. 2019
3. With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing

   Avery Miller, Boaz Patt-Shamir, and Will Rosenbaum

   In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019. 2019
4. Fault Tolerant Gradient Clock Synchronization

   Johannes Bund, Christoph Lenzen, and Will Rosenbaum

   In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019. 2019
5. Space-Optimal Packet Routing on Trees

   Boaz Patt-Shamir, and Will Rosenbaum

   In 2019 IEEE Conference on Computer Communications, INFOCOM 2019, Paris, France, April 29 - May 2, 2019 2019

2018

1. Lower Bounds for Approximating Graph Parameters via Communication Complexity

   Talya Eden, and Will Rosenbaum

   In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA 2018
2. On Sampling Edges Almost Uniformly

   Talya Eden, and Will Rosenbaum

   In 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA 2018

2017

1. The Space Requirement of Local Forwarding on Acyclic Networks

   Boaz Patt-Shamir, and Will Rosenbaum

   In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017 2017
2. Space-Time Tradeoffs for Distributed Verification

   Rafail Ostrovsky, Mor Perry, and Will Rosenbaum

   In Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO 2017, Porquerolles, France, June 19-22, 2017, Revised Selected Papers 2017

2016

1. Brief Announcement: Space-Time Tradeoffs for Distributed Verification

   Mor Baruch, Rafail Ostrovsky, and Will Rosenbaum

   In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016 2016
2. Distributed Almost Stable Matchings (PhD Thesis)

   William Bailey Rosenbaum

   2016

2015

1. Fast Distributed Almost Stable Matchings

   Rafail Ostrovsky, and Will Rosenbaum

   In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015 2015
2. A Stable Marriage Requires Communication

   Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, and Will Rosenbaum

   In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015 2015
3. It’s Not Easy Being Three: The Approximability of Three-Dimensional Stable Matching Problems

   Rafail Ostrovsky, and Will Rosenbaum

   In Proceedings of the 3rd International Workshop on Matching Under Preferences 2015