7 citations · 8 across the 13 of their papers we have counts for
4 papers · 1 filter
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…