7 papers
Robust Set Reconciliation via Locality Sensitive Hashing
Michael Mitzenmacher, Tom Morgan
We consider variations of set reconciliation problems where two parties, Alice and Bob, each hold a set of points in a metric space, and the goal is for Bob to conclude with a set…
Directory Reconciliation
Michael Mitzenmacher, Tom Morgan
We initiate the theoretical study of directory reconciliation, a generalization of document exchange, in which Alice and Bob each have different versions of a set of documents that…
Multi-Observation Regression
Rafael Frongillo, Nishant A. Mehta, Tom Morgan +1
Recent work introduced loss functions which measure the error of a prediction based on multiple simultaneous observations or outcomes. In this paper, we explore the theoretical and…
Reconciling Graphs and Sets of Sets
Michael Mitzenmacher, Tom Morgan
We explore a generalization of set reconciliation, where the goal is to reconcile sets of sets. Alice and Bob each have a parent set consisting of child sets, each containing a…
Multi-Observation Elicitation
Sebastian Casalaina-Martin, Rafael Frongillo, Tom Morgan +1
We study loss functions that measure the accuracy of a prediction based on multiple data points simultaneously. To our knowledge, such loss functions have not been studied before i…
A note on reductions between compressed sensing guarantees
Tom Morgan, Jelani Nelson
In compressed sensing, one wishes to acquire an approximately sparse high-dimensional signal via noisy linear measurements, then later approximately rec…