6 papers
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…