Optimality of correlated sampling strategies

DOI10.4086/TOC.2020.V016A012MaRDI QIDQ5140847zbMATH OpenOpenAlexFDO

Authors Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan

Publication date 17 December 2020

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1612.01041

zbMATH Keywords

communication complexitycorrelated samplingcouplingdistributionsMinHashsampling

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Communication complexity, information complexity (68Q11) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Distributed algorithms (68W15)

Abstract: 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 $2delta/(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. In this paper, we give a surprisingly simple proof that this strategy is essentially optimal. Specifically, for every $deltain(0,1)$, we show that any correlated sampling strategy incurs a disagreement probability of essentially $2delta/(1+delta)$ on some inputs $P$ and $Q$ with total variation distance at most $delta$. This partially answers a recent question of Rivest. Our proof is based on studying a new problem that we call "constrained agreement". Here, the two players are given subsets $Asubseteq[n]$ and $Bsubseteq[n]$, respectively, and their goal is to output an element $iinA$ and $jinB$, respectively, while minimizing the probability that $ieqj$. We prove tight bounds for this question, which in turn imply tight bounds for correlated sampling. Though we settle basic questions about the two problems, our formulation leads to more fine-grained questions that remain open.

Recommendations

• Communication complexity of estimating correlations
• Non interactive simulation of correlated distributions is decidable
• A lower bound for sampling disjoint sets
• Communication complexity of statistical distance
• Communication complexity of statistical distance

Cites work

• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Parallel repetition in projection games and a concentration bound
• Parallel repetition: simplification and the no-signaling case
• Probability and Computing

Cited in

(3)

• Sampling strategy for optimal classification into one of two correlated normal populations
• Non interactive simulation of correlated distributions is decidable
• Parallelize single-site dynamics up to Dobrushin criterion

This page was built for publication: Optimality of correlated sampling strategies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140847)