1 citations · 2 across the 25 of their papers we have counts for
6 papers · 1 filter
Characterizing the Distinguishability of Product Distributions through Multicalibration
Cassandra Marcussen, Aaron Putterman, Salil Vadhan
Given a sequence of samples promised to be drawn from one of two distributions , a well-studied problem in statistics is to decide dis…
Bivariate Linear Operator Codes
Aaron L. Putterman, Vadim Zaripov
In this work, we present a generalization of the linear operator family of codes that captures more codes that achieve list decoding capacity. Linear operator (LO) codes were intro…
Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
William Kuszmaul, Aaron Putterman, Tingqiang Xu +2
Retrieval data structures are data structures that answer key-value queries without paying the space overhead of explicitly storing keys. The problem can be formulated in four sett…
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…