5 papers
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…
Finding the root in random nearest neighbor trees
Anna Brandenberger, Cassandra Marcussen, Elchanan Mossel +1
We study the inference of network archaeology in growing random geometric graphs. We consider the root finding problem for a random nearest neighbor tree in dimension $d \in \mathb…
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 (…