Fetching the paper…

Reading the bibliography…

Optimality of Correlated Sampling Strategies · Around

2016

Optimality of Correlated Sampling Strategies

Bavarian, Mohammad, Ghazi, Badih, Haramaty, Elad et al.

Original
PDF
Post on X

Understand

In the "correlated sampling" problem, two players are given probability distributions $P$ and $Q$, respectively, over the same finite set, with access to shared randomness.

Without any communication, the two players are each required to output an element sampled according to their respective distributions, while trying to minimize the probability that their outputs disagree.
A well known strategy due to Kleinberg-Tardos and Holenstein, with a close variant (for a similar problem) due to Broder, solves this task with disagreement probability at most $2 \delta/(1+\delta)$, where $\delta$ is the total variation distance between $P$ and $Q$.
This strategy has been used in several different contexts, including sketching algorithms, approximation algorithms based on rounding linear programming relaxations, the study of parallel repetition and cryptography.

Built on

Finding similar files in a large file system
Udi Manber · 1994
Earlier work this paper cites.
On the resemblance and containment of documents
Andrei Z. Broder · 1997
Earlier work this paper cites.
Coupling, Stationarity, and Regeneration
Hermann Thorisson · 2000
Earlier work this paper cites.
A Course in Combinatorics
Jacobus Hendricus van Lint and Richard Michael Wilson · 2001
Earlier work this paper cites.
Similarity estimation techniques from rounding algorithms
Moses S. Charikar · 2002
Earlier work this paper cites.

Similar

Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields
Jon Kleinberg and Éva Tardos · 2002
Cited alongside, same era.
Probability and Computing: Randomized Algorithms and Probabilistic Analysis
Michael Mitzenmacher and Eli Upfal · 2005
Cited alongside, same era.
A dictionary for approximate string search and longest prefix search
Sreenivas Gollapudi and Rina Panigrahy · 2006
Cited alongside, same era.
Rounding parallel repetitions of unique games
Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, and David Steurer · 2008
Cited alongside, same era.
Parallel repetition: simplifications and the no-signaling case
Thomas Holenstein · 2009
Cited alongside, same era.

Then

Consistent weighted sampling
Mark Manasse, Frank McSherry, and Kunal Talwar · 2010
Later among the works it cites.
Parallel repetition in projection games and a concentration bound
Anup Rao · 2011
Later among the works it cites.
Consistent weighted sampling made fast, small, and easy, 2014
Bernhard Haeupler, Mark Manasse, and Kunal Talwar · 2014
Later among the works it cites.
Symmetric Encryption via Keyrings and ECC, 2016
Ronald L. Rivest · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…