69 citations · 144 across the 20 of their papers we have counts for
24 papers
More Efficient Parallel -Edge Coloring
Jeremy T. Fineman, Seyed Ali Mohammadi
This paper gives two parallel algorithms for edge coloring, where denotes the maximum degree of any vertex. The first is a deterministic parallel algorithm with $\tilde{O…
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…
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…
Nested Active-Time Scheduling
Nairen Cao, Jeremy T. Fineman, Shi Li +3
The active-time scheduling problem considers the problem of scheduling preemptible jobs with windows (release times and deadlines) on a parallel machine that can schedule up to …
Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths
Nairen Cao, Jeremy T. Fineman, Katina Russell
The approximate single-source shortest-path problem is as follows: given a graph with nonnegative edge weights and a designated source vertex , return estimates of the distances…
Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
Guy E. Blelloch, Jeremy T. Fineman, Yan Gu +1
In this paper we develop optimal algorithms in the binary-forking model for a variety of fundamental problems, including sorting, semisorting, list ranking, tree contraction, range…
Efficient Race Detection with Futures
Robert Utterback, Kunal Agrawal, Jeremy Fineman +1
This paper addresses the problem of provably efficient and practically good on-the-fly determinacy race detection in task parallel programs that use futures. Prior works determinac…
Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
Jeremy T. Fineman
One of the simplest problems on directed graphs is that of identifying the set of vertices reachable from a designated source vertex. This problem can be solved easily sequentially…
Implicit Decomposition for Write-Efficient Connectivity Algorithms
Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman +4
The future of main memory appears to lie in the direction of new technologies that provide strong capacity-to-performance ratios, but have write operations that are much more expen…
Sorting with Asymmetric Read and Write Costs
Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons +2
Emerging memory technologies have a significant gap between the cost, both in time and in energy, of writing to memory versus reading from memory. In this paper we present models a…
Efficient Algorithms with Asymmetric Read and Write Costs
Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons +2
In several emerging technologies for computer memory (main memory), the cost of reading is significantly cheaper than the cost of writing. Such asymmetry in memory costs poses a fu…
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…
Cost-oblivious storage reallocation
Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete +2
Databases need to allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in…
Cache-Oblivious Persistence
Pooya Davoodi, Jeremy T. Fineman, John Iacono +1
Partial persistence is a general transformation that takes a data structure and allows queries to be executed on any past state of the structure. The cache-oblivious model is the l…
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…
Reallocation Problems in Scheduling
Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete +2
In traditional on-line problems, such as scheduling, requests arrive over time, demanding available resources. As each request arrives, some resources may have to be irrevocably co…
Greedy Sequential Maximal Independent Set and Matching are Parallel on Average
Guy Blelloch, Jeremy Fineman, Julian Shun
The greedy sequential algorithm for maximal independent set (MIS) loops over the vertices in arbitrary order adding a vertex to the resulting set if and only if no previous neighbo…
A New Approach to Incremental Cycle Detection and Related Problems
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert +1
We consider the problem of detecting a cycle in a directed graph that grows by arc insertions, and the related problems of maintaining a topological order and the strong components…
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…