1 citations · 1 across the 8 of their papers we have counts for
10 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…
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…
Spectral non-concentration near the top for unimodular random graphs
Mikolaj Fraczyk, Ben Hayes, Madhu Sudan +1
In recent work on equiangular lines, Jiang, Tidor, Yuan, Zhang, and Zhao showed that a connected bounded degree graph has sublinear second eigenvalue multiplicity. More generally t…
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…
Errors are Robustly Tamed in Cumulative Knowledge Processes
Anna Brandenberger, Cassandra Marcussen, Elchanan Mossel +1
We study processes of societal knowledge accumulation, where the validity of a new unit of knowledge depends both on the correctness of its derivation and on the validity of the un…