8 citations · 17 across the 10 of their papers we have counts for
15 papers
Parallel Batch-Dynamic Maximal Independent Set
Guy Blelloch, Andrew Brady, Laxman Dhulipala +2
We develop the first theoretically-efficient algorithm for maintaining the maximal independent set (MIS) of a graph in the parallel batch-dynamic setting. In this setting, a graph…
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…
Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
Michael Dinitz, Jeremy T. Fineman, Seeun William Umboh
This paper considers using predictions in the context of the online Joint Replenishment Problem with Deadlines (JRP-D). Prior work includes asymptotically optimal competitive ratio…
Single-Source Shortest Paths with Negative Real Weights in Time
Jeremy T. Fineman
This paper presents a randomized algorithm for the problem of single-source shortest paths on directed graphs with real (both positive and negative) edge weights. Given an input gr…
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…
Self-supervised Representation Learning on Electronic Health Records with Graph Kernel Infomax
Hao-Ren Yao, Nairen Cao, Katina Russell +3
Learning Electronic Health Records (EHRs) representation is a preeminent yet under-discovered research topic. It benefits various clinical decision support applications, e.g., medi…