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