7 citations · 8 across the 13 of their papers we have counts for
15 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…
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…
Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
Sanjeev Khanna, Aaron Putterman, Madhu Sudan
We study the problem of constructing hypergraph cut sparsifiers in the streaming model where a hypergraph on vertices is revealed either via an arbitrary sequence of hyperedge…
A Theory of Spectral CSP Sparsification
Sanjeev Khanna, Aaron Putterman, Madhu Sudan
We initiate the study of spectral sparsification for instances of Constraint Satisfaction Problems (CSPs). In particular, we introduce a notion of the \emph{spectral energy} of a f…
Streaming Maximal Matching with Bounded Deletions
Sanjeev Khanna, Christian Konrad, Jacques Dark
We initiate the study of the Maximal Matching problem in bounded-deletion graph streams. In this setting, a graph is revealed as an arbitrary sequence of edge insertions and de…
Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
Sanjeev Khanna, Huan Li, Aaron Putterman
A hypergraph spectral sparsifier of a hypergraph is a weighted subgraph that approximates the Laplacian of to a specified precision. Recent work has shown that similar…
Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
Sanjeev Khanna, Aaron L. Putterman, Madhu Sudan
A -sparsifier of a hypergraph is a (weighted) subgraph that preserves the value of every cut to within a -factor. It is known that every hypergraph w…
Efficient Algorithms and New Characterizations for CSP Sparsification
Sanjeev Khanna, Aaron L. Putterman, Madhu Sudan
CSP sparsification, introduced by Kogan and Krauthgamer (ITCS 2015), considers the following question: how much can an instance of a constraint satisfaction problem be sparsified (…
Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
Arpit Agarwal, Sanjeev Khanna, Huan Li +4
We present a parallel algorithm for the -approximate maximum flow problem in capacitated, undirected graphs with vertices and edges, achieving $O(ε^{-3}\text{polylog…
Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
Sanjeev Khanna, Aaron L. Putterman, Madhu Sudan
Recently, a number of variants of the notion of cut-preserving hypergraph sparsification have been studied in the literature. These variants include directed hypergraph sparsificat…
Code Sparsification and its Applications
Sanjeev Khanna, Aaron L Putterman, Madhu Sudan
We introduce a notion of code sparsification that generalizes the notion of cut sparsification in graphs. For a (linear) code of dimension $k…