4 papers
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…
Fast and Compact Sketch-Based Dynamic Connectivity
Quinten De Man, Qamber Jafri, Daniel Delayo +3
We study the dynamic connectivity problem for massive, dense graphs. Our goal is to build a system for dense graphs that simultaneously answers connectivity queries quickly, mainta…
Parallel GPU-Accelerated Randomized Construction of Approximate Cholesky Preconditioners
Tianyu Liang, Chao Chen, Yotam Yaniv +5
We introduce a parallel algorithm to construct a preconditioner for solving a large, sparse linear system where the coefficient matrix is a Laplacian matrix (a.k.a., graph Laplacia…
The Case for External Graph Sketching
Michael A. Bender, MartÃn Farach-Colton, Riko Jacob +3
Algorithms in the data stream model use space to compute some property of an input of size , and many of these algorithms are implemented and used in practice. H…