1 citations · 2 across the 25 of their papers we have counts for
8 papers · 1 filter
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…
Sparsifying Cayley Graphs on Every Group
Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty +2
A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a cut (or spectral) sparsifier which prese…
Tight Bounds for Sparsifying Random CSPs
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
The problem of CSP sparsification asks: for a given CSP instance, what is the sparsest possible reweighting such that for every possible assignment to the instance, the number of s…
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…
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…
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…