69 citations · 144 across the 20 of their papers we have counts for
6 papers · 1 filter
Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation
Guy Blelloch, Andrew Brady, Laxman Dhulipala +3
A low out-degree orientation directs each edge of an undirected graph with the goal of minimizing the maximum out-degree of a vertex. In the parallel batch-dynamic setting, one can…
Fully Energy-Efficient Randomized Backoff: Slow Feedback Loops Yield Fast Contention Resolution
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert +2
Contention resolution addresses the problem of coordinating access to a shared channel. Time proceeds in slots, and a packet transmission can be made in any slot. A packet is succe…
Smoothed Analysis of Information Spreading in Dynamic Networks
Michael Dinitz, Jeremy Fineman, Seth Gilbert +1
The best known solutions for -message broadcast in dynamic networks of size require rounds. In this paper, we see if these bounds can be improved by smoothed analysi…
Smoothed Analysis of Dynamic Networks
Michael Dinitz, Jeremy T. Fineman, Seth Gilbert +1
We generalize the technique of smoothed analysis to distributed algorithms in dynamic network models. Whereas standard smoothed analysis studies the impact of small random perturba…
How to Scale Exponential Backoff
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert +1
Randomized exponential backoff is a widely deployed technique for coordinating access to a shared resource. A good backoff protocol should, arguably, satisfy three natural properti…
Improved Approximations for Multiprocessor Scheduling Under Uncertainty
Christopher Crutchfield, Zoran Dzunic, Jeremy T. Fineman +2
This paper presents improved approximation algorithms for the problem of multiprocessor scheduling under uncertainty, or SUU, in which the execution of each job may fail probabilis…