7 citations · 18 across the 15 of their papers we have counts for
4 papers · 1 filter
Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
Will Rosenbaum, Jukka Suomela
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 t…
The Arboricity Captures the Complexity of Sampling Edges
Talya Eden, Dana Ron, Will Rosenbaum
In this paper, we revisit the problem of sampling edges in an unknown graph from a distribution that is (pointwise) almost uniform over . We consider the case where…
With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing
Avery Miller, Boaz Patt-Shamir, Will Rosenbaum
We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate and burstiness . In this model, we analyze th…
Fault Tolerant Gradient Clock Synchronization
Johannes Bund, Christoph Lenzen, Will Rosenbaum
Synchronizing clocks in distributed systems is well-understood, both in terms of fault-tolerance in fully connected systems and the dependence of local and global worst-case skews…