Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2025
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 w…
cs.DS2025
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…