6 papers
Truly Work-efficient Parallel Deterministic -coloring and Maximal Independent Set
Chase Hutton, Adam Melrod
We give deterministic parallel algorithms that compute a -coloring and a maximal independent set for a simple graph with vertices and edges in work and $O(\…
On Randomized Algorithms in Online Strategic Classification
Chase Hutton, Adam Melrod, Han Shao
Online strategic classification studies settings in which agents strategically modify their features to obtain favorable predictions. For example, given a classifier that determine…
High Probability Work Efficient Parallel Algorithms
Chase Hutton, Adam Melrod
Randomized parallel algorithms for many fundamental problems achieve optimal linear work in expectation, but upgrading this guarantee to hold with high probability (whp) remains a…
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…
Parallel Batch Dynamic Vertex Coloring in Amortized Update Time
Chase Hutton, Adam Melrod
We present the first parallel batch-dynamic algorithm for maintaining a proper -vertex coloring. Our approach builds on a new sequential dynamic algorithm inspired by the…
Encoding Schemes for Parallel In-Place Algorithms
Chase Hutton, Adam Melrod
Many parallel algorithms which solve basic problems in computer science use auxiliary space linear in the input to facilitate conflict-free computation. There has been significant…