1 citations · 1 across the 8 of their papers we have counts for
8 papers · 1 filter
Deterministic Connectivity Sketches Under Edge Deletions
Sanjeev Khanna, Aaron Putterman, Madhu Sudan
How much information about a graph is needed to determine its connectivity after arbitrary valid edge deletions? This question is at the heart of designing deterministic dynamic st…
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…
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…
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 (…
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…