28 citations · 86 across the 41 of their papers we have counts for
40 papers · 1 filter
Fast and Theoretically-Efficient Batch-Parallel Link-Cut Trees, Euler Tour Trees, and Treaps
Quinten De Man, Laxman Dhulipala
Parallel batch-dynamic trees are a fundamental building block in recent theoretical and practical advances in dynamic graph algorithms. However, all existing parallel batch-dynamic…
Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
Quinten De Man, Gilvir Gill, Michael A. Bender +2
Dynamic connectivity is a fundamental dynamic graph problem, and recent algorithmic breakthroughs on dynamic graph sketching have reshaped what is theoretically possible: by encodi…
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…
UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees
Quinten De Man, Atharva Sharma, Kishen N Gowda +1
The dynamic trees problem is to maintain a tree under edge updates while supporting queries like connectivity queries or path queries. Despite the first data structure for this fun…
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
Laxman Dhulipala, Monika Henzinger, George Z. Li +3
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the $k…
Parallel Hierarchical Agglomerative Clustering in Low Dimensions
MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher +4
Hierarchical Agglomerative Clustering (HAC) is an extensively studied and widely used method for hierarchical clustering in based on repeatedly merging the closest p…