11 papers
Reachability in Directed Acyclic Graphs with Near-Linear Cut Queries
Sanjeev Khanna, Aaron Putterman, Junkai Song
In the cut-query model, an algorithm is given access to a graph \emph{only} via cut queries. This model has seen significant attention in the undirected graph setting,…
A Unified Theory of Sparsification
Sanjeev Khanna, Aaron Putterman, Madhu Sudan
We study the sparsifiability of \emph{real-valued codes}, a unifying abstraction that generalizes both combinatorial and continuous notions of sparsification, including spectral sp…
An Round Parallel Algorithm for Matroid Bases
Sanjeev Khanna, Aaron Putterman, Junkai Song
We study the parallel (adaptive) complexity of the classic problem of finding a basis in an -element matroid, given access via an \emph{independence oracle}. In this model, the…
Fault-Tolerant Distance Oracles Below the Barrier
Sanjeev Khanna, Christian Konrad, Aaron Putterman
Fault-tolerant spanners are fundamental objects that preserve distances in graphs even under edge failures. A long line of work culminating in Bodwin, Dinitz, Robelle (SODA 2022) g…
Optimal Parallel Basis Finding in Graphic and Related Matroids
Sanjeev Khanna, Aaron Putterman, Junkai Song
We study the parallel complexity of finding a basis of a graphic matroid under independence-oracle access. Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988) initiated the study of…
On the Parallel Complexity of Finding a Matroid Basis
Sanjeev Khanna, Aaron Putterman, Junkai Song
A fundamental question in parallel computation, posed by Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988), asks: \emph{given only independence-oracle access to a matroid on el…