4 papers
A Near-Optimal Parallel Algorithm for Finding Matroid Bases
Sanjeev Khanna, Aaron Putterman, Junkai Song
We settle the classic question of the parallel complexity of computing a matroid basis, as first posed in the seminal work of Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988). Our…
A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
Julia Chuzhoy, Sanjeev Khanna, Junkai Song
In the fully dynamic maximal matching problem, the goal is to maintain a maximal matching in a graph undergoing an online sequence of edge insertions and deletions. The problem has…
Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
Sepehr Assadi, Sanjeev Khanna, Aaron Putterman
Correlation clustering is a widely-used approach for clustering large data sets based only on pairwise similarity information. In recent years, there has been a steady stream of be…
Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
Sepehr Assadi, Sanjeev Khanna, Peter Kiss
In a very recent breakthrough, Behnezhad and Ghafari [FOCS'24] developed a novel fully dynamic randomized algorithm for maintaining a -approximation of maximum matching wit…