The Optimality of Correlated Sampling
Mohammad Bavarian\thanks{ Department of Mathematics and Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology
Cambridge MA 02139. Supported in part by NSF Award CCF-1420692. {\tt bavarian@mit.edu
abstract.tex
\abstract{

In the \emph{correlated sampling} problem, two players, say Alice and Bob,
are given two distributions, say $P$ and $Q$ respectively,
over the same universe and access to shared randomness.
The two players are required to output two elements, without any interaction,
sampled according to their respective distributions, while trying to minimize the
probability that their outputs disagree.
A well-known protocol due to Holenstein, with close variants (for similar problems) due to Broder, and to Kleinberg and Tardos, solves this task with disagreement probability at most $2 \delta/(1+\delta)$, where $\delta$ is the total variation distance between $P$ and $Q$. This protocol 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 note, we give a surprisingly simple proof that this protocol is in fact tight. Specifically, for every $\delta \in (0,1)$, we show that any correlated sampling scheme should have disagreement probability at least $2\delta/(1+\delta)$. This partially answers a recent question of Rivest.

Our proof is based on studying a new problem we call \emph{constrained agreement}. Here, Alice is given a subset $A \subseteq [n]$ and is required to output an element $i \in A$, Bob is given a subset $B \subseteq [n]$ and is required to output an element $j \in B$, and the goal is to minimize the probability that $i \neq j$. We prove tight bounds on this question, which turn out to imply tight bounds for correlated sampling.
Though we settle basic questions about the two problems, our formulation also leads
to several questions that remain open.}

\iffalse
Plain-text abstract:
In the "correlated sampling" problem, two players, say Alice and Bob, are given two distributions, say $P$ and $Q$ respectively,
over the same universe and access to shared randomness. The two players are required to output two elements, without any interaction,
sampled according to their respective distributions, while trying to minimize the probability that their outputs disagree. A well-known protocol due to Holenstein, with close variants (for similar problems) due to Broder, and to Kleinberg and Tardos, solves this task with disagreement probability at most $2 \delta/(1+\delta)$, where $\delta$ is the total variation distance between $P$ and $Q$. This protocol 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 note, we give a surprisingly simple proof that this protocol is in fact tight. Specifically, for every $\delta \in (0,1)$, we show that any correlated sampling scheme should have disagreement probability at least $2\delta/(1+\delta)$. This partially answers a recent question of Rivest.

Our proof is based on studying a new problem we call "constrained agreement". Here, Alice is given a subset $A \subseteq [n]$ and is required to output an element $i \in A$, Bob is given a subset $B \subseteq [n]$ and is required to output an element $j \in B$, and the goal is to minimize the probability that $i \neq j$. We prove tight bounds on this question, which turn out to imply tight bounds for correlated sampling. Though we settle basic questions about the two problems, our formulation also leads to several questions that remain open.
\fi
correlated_sampling_itcs.tex
\def \defmargin{2cm}

\RequirePackage[]{silence}
\WarningsOff[hyperref]

%\documentclass[12pt]{article}

\providecommand{\report}{0} %If you want report then do "\def \report{1}" before importing template.
\providecommand{\deffontsize}{11pt} % If 12pt is preferred, do "\def \deffontsize{12pt}" or such, before importing template.

\ifnum \report=1
\documentclass[xelatex, \deffontsize]{report}
\else
\documentclass[xelatex, \deffontsize]{article}
\fi


% Packages
\usepackage{amsmath, amssymb, amsthm, amsfonts, bbm}
\usepackage[tbtags]{mathtools}
\usepackage{thmtools}
\usepackage{thm-restate}
\usepackage{graphicx}
\usepackage{verbatim}
%\usepackage{framed}
\usepackage{enumerate}
\usepackage{palatino}
%\usepackage[symbol,stable]{footmisc}
\usepackage[usenames,dvipsnames]{color}
\usepackage{units}
\usepackage{tikz}
\usepackage{subfigure}
\usepackage{setspace}
\usepackage{enumitem}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage[charter]{mathdesign}
\usepackage[pdfstartview=FitH, pdfpagemode=None, colorlinks=true, citecolor=blue, linkcolor=blue, urlcolor=magenta, pagebackref=true, unicode=false]{hyperref}

\usepackage{hyperref,cleveref}

% Page margins :
\providecommand{\defmargin}{1in} % Do "\def \defmargin{2cm}" or such.
\usepackage[top=\defmargin, bottom=\defmargin, left=\defmargin, right=\defmargin]{geometry}

\usepackage{xargs} % Use more than one optional parameter in a new commands
%\usepackage[pdftex,dvipsnames]{xcolor}  % Coloured text etc.
\usepackage[colorinlistoftodos,prependcaption,textsize=footnotesize]{todonotes}

\providecommand{\todotoggle}{0} % "\def \todotoggle{0}" to hide all todos.

\newcommand{\mytodo}[1]{\ifnum\todotoggle=1{#1}\fi}
\newcommand{\mynote}[1]{\mytodo{\Red{#1}}}
\newcommand{\mycomment}[1]{\mytodo{\todo[inline,linecolor=red,backgroundcolor=red!25,bordercolor=red]{#1}}}
\newcommandx{\unsure}[2][1=]{\mytodo{\todo[linecolor=blue,backgroundcolor=blue!25,bordercolor=blue,#1]{#2}}}
\newcommandx{\change}[2][1=]{\mytodo{\todo[linecolor=cyan,backgroundcolor=cyan!25,bordercolor=cyan,#1]{#2}}}
\newcommandx{\info}[2][1=]{\mytodo{\todo[linecolor=green,backgroundcolor=green!25,bordercolor=green,#1]{#2}}}
\newcommandx{\improve}[2][1=]{\mytodo{\todo[linecolor=red,backgroundcolor=red!25,bordercolor=red,#1]{#2}}}
\newcommandx{\thiswillnotshow}[2][1=]{\todo[disable,#1]{#2}}
\newcommand{\tableoftodos}{\ifnum\todotoggle=1 \listoftodos[Comments/To Do's] \fi}

% Tikz commands :
\usetikzlibrary{positioning,snakes,mindmap,calc,fit,arrows,shapes}
\newcommand{\createconcept}[1]{\tikzstyle{currentconcept} = [concept, shade, shading=ball, ball color=#1, draw=none]}
\newcommand{\tikzmark}[1]{\tikz[overlay,remember picture] \node (#1) {};}
\tikzstyle{box} = [shape=rectangle,draw=black,thick]

%\renewcommand{\labelitemi}{$-$}
\newcommand{\zeroitemsep}{\setlength{\itemsep}{0pt}}

% Foot note setting :
%\DefineFNsymbols*{lamportnostar}[math]{\dagger\ddagger\S\P\|{\dagger\dagger}{\ddagger\ddagger}}
%\setfnsymbol{lamportnostar}

%%%%%%%%%%% my-macros %%%%%%%%%%%%%%%%

\newcommand{\myignore}[1]{}

\newcommand{\extraemptypage}{\newpage \thispagestyle{empty} \mbox{}}
\newcommand{\blankpage}{\newpage \mbox{} \newpage}

% Colors:
\newcommand{\TealBlue}[1]{\textcolor{TealBlue}{#1}}
\newcommand{\Peach}[1]{\textcolor{Peach}{#1}}
\newcommand{\Cyan}[1]{\textcolor{cyan}{#1}}
\newcommand{\Red}[1]{\textcolor{red}{#1}}
\newcommand{\Navy}[1]{\textcolor{Blue}{#1}}
\newcommand{\Blue}[1]{\textcolor{Blue}{#1}}
\newcommand{\Green}[1]{\textcolor{OliveGreen}{#1}}
\newcommand{\Black}[1]{\textcolor{black}{#1}}
\newcommand{\White}[1]{\textcolor{white}{#1}}
\newcommand{\Code}[1]{\Cyan{\texttt{#1}}}
\newcommand{\Gray}[1]{\textcolor{gray}{#1}}
\newcommand{\Magenta}[1]{\textcolor{magenta}{#1}}

\newcommand{\tTealBlue}[1]{\ifnum\todotoggle=1\TealBlue{#1}\else{#1}\fi}
\newcommand{\tPeach}[1]{\ifnum\todotoggle=1\Peach{#1}\else{#1}\fi}
\newcommand{\tCyan}[1]{\ifnum\todotoggle=1\Cyan{#1}\else{#1}\fi}
\newcommand{\tRed}[1]{\ifnum\todotoggle=1\Red{#1}\else{#1}\fi}
\newcommand{\tNavy}[1]{\ifnum\todotoggle=1\Navy{#1}\else{#1}\fi}
\newcommand{\tBlue}[1]{\ifnum\todotoggle=1\Blue{#1}\else{#1}\fi}
\newcommand{\tGreen}[1]{\ifnum\todotoggle=1\Green{#1}\else{#1}\fi}
\newcommand{\tBlack}[1]{\ifnum\todotoggle=1\Black{#1}\else{#1}\fi}
\newcommand{\tWhite}[1]{\ifnum\todotoggle=1\White{#1}\else{#1}\fi}
\newcommand{\tCode}[1]{\ifnum\todotoggle=1\Code{#1}\else{#1}\fi}
\newcommand{\tGray}[1]{\ifnum\todotoggle=1\Gray{#1}\else{#1}\fi}
\newcommand{\tMagenta}[1]{\ifnum\todotoggle=1\Magenta{#1}\else{#1}\fi}

% All Bracketting commands :
\newcommand{\inbrace}[1]{\left \{ #1 \right \}}
\newcommand{\inparen}[1]{\left ( #1 \right )}
\newcommand{\insquare}[1]{\left [ #1 \right ]}
\newcommand{\inangle}[1]{\left \langle #1 \right \rangle}
\newcommand{\infork}[1]{\left \{ \begin{matrix} #1 \end{matrix} \right .}
\newcommand{\inmat}[1]{\begin{matrix} #1 \end{matrix}}
\newcommand{\inbmat}[1]{\begin{bmatrix} #1 \end{bmatrix}}
\newcommand{\insqmat}[1]{\insquare{\begin{matrix} #1 \end{matrix}}}
\newcommand{\inabs}[1]{\begin{vmatrix} #1 \end{vmatrix}}
\newcommand{\norm}[2]{\begin{Vmatrix} #2 \end{Vmatrix}_{#1}}

% Floor, Ceiling :
\newcommand{\ceil}[1]{\left \lceil #1 \right \rceil}
\newcommand{\floor}[1]{\left \lfloor #1 \right \rfloor}

% Math operators :
\newcommand{\set}[1]{\inbrace{#1}}
\newcommand{\setdef}[2]{\set{#1 : #2}}
\newcommand{\defeq}{\stackrel{\mathrm{def}}{=}}

\newcommand{\ddx}[2]{\frac{d #1}{d #2}}
\newcommand{\dodox}[2]{\frac{\partial #1}{\partial #2}}

\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\DeclareMathOperator*{\expect}{\mathbb{E}}
\DeclareMathOperator*{\Var}{\mathrm{Var}}

\newcommand{\sAND}{\ \mathrm{and} \ }
\newcommand{\sOR}{\ \mathrm{or} \ }
\newcommand{\sXOR}{\ \mathrm{xor} \ }
\newcommand{\sIF}{\ \mathrm{if} \ }

\newcommand{\union}{\cup}
\newcommand{\intersect}{\cap}

\newcommand{\indicator}{\mathbbm{1}}

\newcommand{\half}{\nicefrac{1}{2}}
\newcommand{\third}{\nicefrac{1}{3}}
\newcommand{\fourth}{\nicefrac{1}{4}}

\newcommand{\bit}{\set{0,1}}
\newcommand{\sbit}{\set{1, -1}}

\newcommand{\wtilde}[1]{\widetilde{#1}}
\newcommand{\what}[1]{\widehat{#1}}

\newcommand{\dTV}{d_{\mathrm{TV}}}

\newcommand{\Ex}{\mathbb E}

% Letters in MathBB :
\newcommand{\bbC}{{\mathbb C}}
\newcommand{\bbE}{{\mathbb E}}
\newcommand{\bbF}{{\mathbb F}}
\newcommand{\bbN}{{\mathbb N}}
\newcommand{\bbP}{{\mathbb P}}
\newcommand{\bbQ}{{\mathbb Q}}
\newcommand{\bbR}{{\mathbb R}}
\newcommand{\bbS}{{\mathbb S}}
\newcommand{\bbZ}{{\mathbb Z}}

% Bold letters :
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bm}{\mathbf{m}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bs}{\mathbf{s}}
\newcommand{\bt}{\mathbf{t}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}

\newcommand{\bX}{\mathbf{X}}
\newcommand{\bY}{\mathbf{Y}}
\newcommand{\bZ}{\mathbf{Z}}

% Letters in Cal :
\newcommand{\calA}{\mathcal{A}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\calC}{\mathcal{C}}
\newcommand{\calD}{\mathcal{D}}
\newcommand{\calE}{\mathcal{E}}
\newcommand{\calF}{\mathcal{F}}
\newcommand{\calG}{\mathcal{G}}
\newcommand{\calH}{\mathcal{H}}
\newcommand{\calI}{\mathcal{I}}
\newcommand{\calJ}{\mathcal{J}}
\newcommand{\calL}{\mathcal{L}}
\newcommand{\calM}{\mathcal{M}}
\newcommand{\calN}{\mathcal{N}}
\newcommand{\calO}{\mathcal{O}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calQ}{\mathcal{Q}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calT}{\mathcal{T}}
\newcommand{\calU}{\mathcal{U}}
\newcommand{\calV}{\mathcal{V}}
\newcommand{\calX}{\mathcal{X}}
\newcommand{\calY}{\mathcal{Y}}
\newcommand{\calZ}{\mathcal{Z}}

\newcommand{\eps}{\varepsilon}

% Words in Mathrm :
\newcommand{\size}{\mathrm{size}}
\newcommand{\depth}{\mathrm{depth}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\ESYM}{\mathrm{ESYM}}
\newcommand{\Inf}{\mathrm{Inf}}
\newcommand{\sign}{\mathrm{sign}}
\newcommand{\Maj}{\mathrm{Maj}}
\newcommand{\Det}{\mathrm{Det}}
\newcommand{\Perm}{\mathrm{Perm}}
\newcommand{\NW}{\mathrm{NW}}
\newcommand{\IMM}{\mathrm{IMM}}
\newcommand{\VP}{\mathrm{VP}}
\newcommand{\VNP}{\mathrm{VNP}}
\newcommand{\ECC}{\mathrm{ECC}}
\newcommand{\IC}{\mathrm{IC}}
\newcommand{\CC}{\mathrm{CC}}
\newcommand{\Supp}{\mathrm{Supp}}
\newcommand{\EQ}{\mathrm{EQ}}

% Special Text Words :
\newcommand{\naive}{na\"{i}ve }
\newcommand{\Hastad}{H{\aa}stad }
\newcommand{\Grobner}{Gr\"{o}bner}
\newcommand{\Madry}{M{\k{a}}dry}
\newcommand{\Lovasz}{Lov\'{a}sz }

% Theorems :
\newtheorem{theorem}{Theorem}[section]
\newtheorem{defn}[theorem]{Definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{lem}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{goal}[theorem]{Goal}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{ex}[theorem]{Exercise}
\newtheorem{question}[theorem]{Question}
\newtheorem{answer}[theorem]{Answer}
\newtheorem{note}[theorem]{Note}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{assumption}[theorem]{Assumption}
%\newtheorem{procedure}[theorem]{Procedure}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{subclaim}[theorem]{Subclaim}
\newtheorem{open}[theorem]{Open Problem}

\newenvironment{solution}[1]{\noindent {\bf Solution #1.} \hspace*{1mm}} {\hfill $\blacksquare$}

% New Environments :
\newenvironment{proof-overview}{\noindent {\em Proof Overview.} \hspace*{1mm}}{\hfill $\Box$}
\newenvironment{proofof}[1]{\noindent {\em Proof of #1.} \hspace*{1mm}}{\hfill $\Box$}
\newenvironment{proof-sketch}{\noindent {\em Sketch of Proof.} \hspace*{1mm}}{\hfill $\Box$}
\newenvironment{proof-idea}{\noindent{\em Proof Idea.}\hspace*{1mm}}{\qed\bigskip}
\newenvironment{proof-attempt}{\noindent{\em Proof Attempt.}\hspace*{1mm}}{\qed\bigskip}
%\newenvironment{remark}{\noindent{\bf Remark.}\hspace*{1em}}{\bigskip}

\usepackage[boxruled]{algorithm2e}

\begin{document}

\title{The Optimality of Correlated Sampling}


\author{
Mohammad Bavarian\thanks{ Department of Mathematics and  Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge MA 02139. Supported in part by NSF Award CCF-1420692. {\tt bavarian@mit.edu}.}
\and
Badih Ghazi\thanks{Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge MA 02139. Supported in part by NSF CCF-1420956, NSF CCF-1420692 and CCF-1217423. {\tt badih@mit.edu}.}
\and
Elad Haramaty\thanks{Harvard John A. Paulson School of Engineering and Applied Sciences. Part of this work supported by NSF Award CCF-1565641.
{\tt seladh@gmail.com}.}%
\and
Pritish Kamath\thanks{Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge MA 02139. Supported in part by NSF CCF-1420956 and NSF CCF-1420692.  {\tt pritish@mit.edu}.}
\and
Ronald L. Rivest\thanks{Institute Professor, MIT. This work supported by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under grant agreement CCF-0939370.}
\and
Madhu Sudan\thanks{Harvard John A. Paulson School of Engineering and Applied Sciences. Part of this work supported by NSF Award CCF-1565641 and a Simons Investigator Award. {\tt madhu@cs.harvard.edu}.}%
}


\maketitle

\input{abstract}
\newpage

\mytodo{
	\tableofcontents
	\tableoftodos
	\newpage
}

\input{intro}

\input{proofs}

\input{protocols}

%\input{old_stuff}

%\bibliographystyle{alpha}
%\bibliography{references}
\input{references.bbl}
\end{document}

intro.tex
\section{Introduction}
In this work, we study \emph{correlated sampling}, a very basic task, variants of which have been considered in the context of sketching algorithms \cite{broder1997resemblance}, approximation algorithms based on rounding linear programming relaxations \cite{kleinberg2002approximation, charikar2002similarity}, the study of parallel repetition \cite{holenstein2007parallel, rao2011parallel, barak2008rounding} and very recently cryptography \cite{Rivest}.

This problem involves two players, Alice and Bob, attempting to come to agreement non-interactively. Alice and Bob are given distributions $P$ and $Q$ respectively over the same universe $\Omega$. Without any interaction, Alice is required to output an element $i \sim P$ and Bob is required to output an element $j \sim Q$, where the players have access to shared randomness. The goal is to minimize the disagreement probability $\Pr[i \neq j]$ in terms of the total variation distance $\dTV(P,Q)$ (where the probability is over the shared randomness). More formally we define {\em correlated sampling strategies} as follows.

\begin{defn}[Correlated Sampling Strategies]\label{def:corr_samp}
	Given a universe\footnote{we will primarily consider only finite universes.} $\Omega$ and a randomness space $\calR$, a pair of functions $(f,g)$, where $f : \Delta_\Omega \times \calR \to \Omega$ and $g : \Delta_\Omega \times \calR \to \Omega$, is said to be a {\em correlated sampling strategy} with error $\eps : [0,1] \to [0,1]$, if for any distribution $P, Q \in \Delta_\Omega$, such that $\dTV(P,Q) = \delta$, it holds that,
	\begin{itemize}
		\item {\bf [Correctness]} $\set{f(P,r)}_{r \sim \calR} = P$ and $\set{g(Q,r)}_{r \sim \calR} = Q$
		\item {\bf [Error guarantee]} $\Pr_{r \sim \calR} \insquare{f(P,r) \ne g(Q,r)} \le \eps(\delta)$
	\end{itemize}
	Here, $\Delta_\Omega$ is the set of all probability distributions on $\Omega$. Also, we abuse notations slightly to let $\calR$ denote a suitable distribution on the set $\calR$. Moreover, we will always assume that $\calR$ is sufficiently large, and we will often not mention $\calR$ explicitly, when talking about correlated sampling strategies. It is also allowed to have a sequence of strategies with increasing size of $\calR$, in which case, we want the above constraints to be satisfied in the limit as $|\calR| \to \infty$.
\end{defn}
 
A priori it is unclear whether such a protocol can even exist, since the error $\eps$ is not allowed to depend on the universe $\Omega$. Somewhat surprisingly, there exists a simple protocol whose disagreement probability can be bounded by roughly twice the total variation distance (and in particular does not degrade with the size of the universe). Variants of this protocol have been rediscovered multiple times in the literature yielding the following theorem.

\begin{theorem}[Holenstein \cite{holenstein2007parallel}. See also 
Broder \cite{broder1997resemblance}, Kleinberg-Tardos \cite{kleinberg2002approximation}]\label{thm:Holest}
For any universe $\Omega$, there exists a correlated sampling strategy with error $\eps : [0,1] \to [0,1]$ such that,
\begin{equation}\label{eq:Holest_bd}
\forall \delta \in [0,1]\;, \quad \quad \eps(\delta) \le \frac{2 \cdot \delta}{1+\delta}
\end{equation}
\end{theorem}

Strictly speaking, the work of Broder~\cite{broder1997resemblance} does not consider the general correlated sampling problem. Rather it gives a strategy (the ``MinHash strategy'') which happens to solve the correlated sampling problem under the condition that $P$ and $Q$ are {\em flat} distributions, i.e. they are uniform over some subset of the domain. The above bound applies to the case where these sets have the same size. The technique can also be generalized to other distributions to get the bound above, and this gives a protocol similar to that of Holenstein, though if $P$ and $Q$ are uniform over different sized subsets, the above bound is weaker than that obtained from a direct application of Broder's algorithm! Holenstein \cite{holenstein2007parallel} appears to be the first to formulate the problem for general distributions and give a solution with the bound claimed above.

For sake of completeness, we give a description of Broder's strategy as well as Holenstein's strategy in Section~\ref{sec:protocols}.  We point out that variants of the protocol in \Cref{thm:Holest} (sometimes referred to as ``consistent sampling'' protocols) had been used in several applied works \cite{manber1994finding,gollapudi2006dictionary, manasse2010consistent} before Holenstein's paper.
%For a self-contained sketch of this protocol, we refer the reader to Section 4.1 of \cite{rao2011parallel}.

Given \Cref{thm:Holest}, a natural and basic question is whether the bound on the disagreement probability can be improved. Indeed, this question was very recently raised by Rivest \cite{Rivest} in the context of symmetric encryption, and this was one of the motivations behind this work. We give a surprisingly simple proof that the bound in \Cref{thm:Holest} is actually
tight (for a coarse parameterization of the problem).

\begin{theorem}[Main Result]\label{thm:main}
For every $\delta \in (0,1)$ and $\gamma > 0$, there exists a family of pairs of distributions $(P,Q)$ satisfying $\dTV(P,Q) \le \delta$ such that any correlated sampling strategy for this family has error at least $\frac{2 \cdot \delta}{1+\delta} - \gamma$.
\end{theorem}
%We note that our result does not show that for every $(P,Q)$, correlated sampling is the best one can do. It simply states that for every $\gamma$ and every strategy there is a sequence of pairs $(P,Q)$ for which the disagreement probability approaches $\frac{2 \cdot \delta}{1+\delta} - \epsilon$.
Our proof of \Cref{thm:main} is surprisingly simple and is based on studying the following \emph{constrained agreement} problem that we introduce and which is tightly related to correlated sampling. Alice is given a subset $A \subseteq [n]$ and Bob is given a subset $B \subseteq [n]$, where the pair $(A,B)$ is sampled from some distribution $\mathcal{D}$. Alice is required to output an element $i \in A$ and Bob is required to output an element $j \in B$, such that the disagreement probability $\Pr_{(A,B) \sim D}[i \neq j]$ is minimized.

\begin{defn}[Constrained Agreement Strategies]\label{def:const_ag}
Given a universe $\Omega = [n]$ and a distribution $\calD$ over $2^\Omega \times 2^\Omega$ (i.e. pairs of subsets of $\Omega$), a pair of functions $(f,g)$, where $f : 2^\Omega \to \Omega$ and $g : 2^\Omega \to \Omega$, is said to be a {\em constrained agreement strategy} with error $\mathrm{err}_{\calD}(f,g) = \eps \in [0,1]$, if it holds that,
\begin{itemize}
	\item {\bf [Correctness]} $\forall A \subseteq \Omega\;, f(A) \in A$ and $\forall B \subseteq \Omega\;, g(B) \in B$
	\item {\bf [Error guarantee]} $\Pr_{(A,B) \sim \calD} \insquare{f(A) \ne g(B)} \le \eps$
\end{itemize}
\end{defn}

We point out that since the constrained agreement problem is defined with respect to an input distribution $\mathcal{D}$ on pairs of sets, we can require, without loss of generality, that the strategies $(f,g)$ be deterministic in \Cref{def:const_ag} (this follows from Yao's minimax principle). We arrive at the constrained agreement problem as follows: First we consider the {\em flat} distribution case of \Cref{def:corr_samp} and relax the restrictions of $\set{f(P,r)}_{r \sim \calR} = P$ and $\set{g(Q,r)}_{r \sim \calR} = Q$, although, we still require that $f(P,r) \in \supp(P)$ and $g(Q,r) \in \supp(Q)$ for any $r \in \calR$. This makes it a constraint satisfaction problem and we consider a distributional version of the same.

In order to prove \Cref{thm:main}, we show that in fact the correlated sampling strategy (a suitable de-randomization thereof) as in \Cref{thm:Holest} is optimal for the constrained agreement problem whenever $\mathcal{D}$ is the distribution $\mathcal{D}_p$ where every coordinate $i \in [n]$ is independently included in each of $A$ and $B$ with probability $p$.

\begin{lem}\label{le:prod_opt}
For every $p \in [0,1]$ and the distribution $\calD_p$ on $2^{[n]} \times 2^{[n]}$, any constrained agreement strategy $(f,g)$ makes error $\mathrm{err}_{\calD_p}(f,g) \ge \frac{2(1-p)}{2-p}$.
%the protocol from \Cref{thm:Holest} is optimal for constrained agreement over $\mathcal{D}_p$, i.e., it has the smallest possible disagreement probability.
\end{lem}

\paragraph{Organization of the paper.} In Section~\ref{sec:special_cases}, we discuss some special cases of correlated sampling problem. In Section~\ref{sec:discussions}, we give some open problems regarding these special cases. In \Cref{sec:pf_main}, we prove \Cref{le:prod_opt} and use it to prove \Cref{thm:main}. In \Cref{sec:protocols}, we describe the correlated sampling protocols of Broder and Holenstein, thereby proving \Cref{thm:Holest}.

\subsection{Special Cases} \label{sec:special_cases}
Let $A, B \subseteq [n]$ be such that $|A| = |B|$, and consider the problem of correlated sampling with the uniform distributions $P = \mathcal{U}(A)$ and $Q = \mathcal{U}(B)$. Then, the total variation distance between $P$ and $Q$ is given by
\begin{equation*}
\dTV(P,Q) = \frac{1}{2} \cdot \| P - Q \|_1 = \frac{1}{2} \cdot \| \mathcal{U}(A) - \mathcal{U}(B) \|_1 = 1 - \frac{|A \cap B|}{|A|}.
\end{equation*}
Thus, the error probability of the correlated sampling strategy (in \Cref{thm:Holest}) is given by
\begin{equation}\label{eq:std_spe}
\frac{2 \cdot \dTV(P,Q)}{1+\dTV(P,Q)} = 1 - \frac{|A \cap B|}{|A \cup B|}
\end{equation}
Rather surprisingly, in the particular case where $|A \cap B| = 1$ and $A \cup B = [n]$, Rivest~\cite{Rivest} recently gave a protocol with smaller error probability than the one guaranteed by the correlated sampling protocol of \Cref{thm:Holest}.

\begin{theorem}[\cite{Rivest}]\label{thm:rivest}
In Definition~\ref{def:corr_samp}, if $\Omega = [n]$, and the distributions $P$ and $Q$ are promised to be of the following form, that there exist $A, B \subseteq [n]$ such that $|A| = |B|$, $|A \cap B| = 1$, $A \cup B = [n]$, and $P = \mathcal{U}(A)$ and $Q  = \mathcal{U}(B)$. Then, there is a correlated sampling strategy with error probability at most $1 - 1/|A|$.
\end{theorem}
\noindent For completeness, we describe this strategy in \Cref{sec:special_protocols}. Note that for this setting of parameters, we have that
\begin{equation*}
1 - \frac{1}{|A|} < 1 - \frac{|A \cap B|}{|A \cup B|} = 1 - \frac{1}{n},
\end{equation*}
and hence \Cref{thm:rivest} improves on the performance (\cref{eq:std_spe}) of the correlated sampling strategy of \Cref{thm:Holest}. This naturally leads to the question: Can one similarly improve on the well-known correlated sampling protocol for larger intersection sizes, for example, when $|A \cap B|$ is a constant fraction of $|A|$? The proof of our main result (\Cref{thm:main}) answers this question negatively. Namely, it implies that the strategy in \Cref{thm:Holest} is tight when $|A \cap B| = \eps \cdot |A|$ with $\eps \in (0,1)$ being an absolute constant.

Note that in the extreme case where $\eps$ is very close to $0$, Rivest's protocol (\Cref{thm:rivest}) implies that \Cref{thm:Holest} is not tight. What about the other extreme where $\eps$ is very close to $1$? We show that in this case \Cref{thm:Holest} is in fact tight.

\begin{theorem}\label{thm:opt_large_inter}
Let $A, B \subseteq [n]$ be such that $A \cup B = [n]$ and $|A| = |B| = |A \cap B| + 1$, and let $P = \mathcal{U}(A)$ and $Q  = \mathcal{U}(B)$. Then, the error probability of any correlated sampling strategy is at least $1 - |A \cap B|/|A \cup B|$.
\end{theorem}

\noindent We prove \Cref{thm:opt_large_inter} in \Cref{sec:large_int_pf}.

\subsection{Open questions and Future work}\label{sec:discussions}

%We start with some concrete open questions before moving on to a vaguer one.
Our work started with a conjecture due to Rivest~\cite{Rivest} which informally asserts that Broder's MinHash strategy is optimal except in the case considered in \Cref{thm:rivest}. More formally,

\begin{conjecture}[Rivest~\cite{Rivest}]
For every collection of positive integers $n,a,b,\ell$ with $\ell \geq 2$ and $n \geq a+b - \ell$, and for every pair of probabilistic strategies $(f,g)$ that satisfy correctness as in \Cref{def:corr_samp}, there exist $A,B \subseteq [n]$ with $|A| = a$, $|B| = b$ and $|A \cap B| = \ell$ such that $$\Pr[f(A) \ne g(B)] \geq 1 - \frac{\ell}{a+b-\ell} = 1 - \frac{|A \cap B|}{|A \cup B|}$$
\end{conjecture}

Our work does not resolve this conjecture for the general setting of $n$, $a$, $b$ and $\ell$. It suggests this answer may be asymptotically right as $n \to \infty$ when $a =\alpha n$, $b = \beta n$ and $\ell = \alpha \beta n$, but does not even resolve this setting. (Our set sizes are only approximately $\alpha n$ etc.)

Even in the setting where the set sizes are allowed to vary slightly, our knowledge is somewhat incomplete. \Cref{le:prod_opt} shows optimality of the MinHash strategy when $(A,B) \sim \calD_p$. In this case, $A$ and $B$ are independent and $p$-biased each, so $|A| \approx p \cdot n$, $|B| \approx p \cdot n$ and $|A \cap B| \approx p^2 \cdot n$. We point out that a simple reduction to \Cref{le:prod_opt} also implies the optimality of the well-known protocol in the case where $A$ and $B$ are ``positively-correlated''. Specifically, consider the following distribution $\mathcal{D}_{p,\delta}$ on pairs $(A,B)$ of subsets of $[n]$, where we first sample $S \subseteq [n]$ which independently includes each element of $[n]$ with probability $p/(1-\delta)$, and then independently including every $i \in S$ in each of $A$ and $B$ with probability $1-\delta$. In this case, $|A| \approx p \cdot n$, $|B| \approx p \cdot n$ and $|A \cap B| \approx (1-\delta) \cdot p \cdot n$. Even if we reveal $S$ to both Alice and Bob, \Cref{le:prod_opt} implies a lower bound of $2\cdot\delta/(1+\delta)$ on the error probability, which is achieved by the MinHash strategy. It is not clear how to use a similar reduction to show optimality in the case where $A$ and $B$ are ``negatively-correlated'', i.e., when $|A| \approx p \cdot n$, $|B| \approx p \cdot n$ and $|A \cap B| \ll p^2 \cdot n$.

Finally the fact that Holenstein's strategy for correlated sampling can be improved upon in the case where $P$ and $Q$ are uniform distributions on different-sized subsets of the universe clearly shows that strategy as in \Cref{thm:Holest} is not ``always optimal''. To study questions like this, one could restrict the class of pairs $(P,Q)$ and then give an optimal strategy for every $P$ and every $Q$. It would be interesting to study what would be the right measure that captures the minimal error probability given the adjacency relationship $(P,Q)$.
proofs.tex
\section{Lower Bounds on Correlated Sampling}\label{sec:pf_main}
We start by proving lower bounds on error probability in the constrained agreement problem.

\begin{proof}[Proof of \Cref{le:prod_opt}]
Let $p \in [0,1]$ and consider the distribution $\mathcal{D}_p$ on pairs $(A,B)$ of subsets $A,B \subseteq [n]$ where for each $i \in [n]$, we independently inlcude $i$ in each of $A$ and $B$ with probability $p$. Let $f$ be Alice's strategy which satisfies the property that $f(A) \in A$ for every $A \subseteq [n]$. Similarly, let $g$ be Bob's strategy which satisfies the property that $g(B) \in B$ for every $B \subseteq [n]$.

%We will construct functions $f^*$ and $g^*$ such that the disagreement probability achieved by strategy pair $(f,g)$ is no less than that achieved by strategy pair $(f^*, g)$ and similarly the disagreement probability achieved by strategy pair $(f^*,g)$ is no less than that achieved by strategy pair $(f^*, g^*)$.
%Moreover, $(f^*,g^*)$ will be such that of the same form as the protocol in \Cref{thm:Holest}, and hence this proves its optimality.
We will construct functions $f^*$ and $g^*$ such that
$$\mathrm{err}_{\calD_p}(f,g) \ge \mathrm{err}_{\calD_p}(f^*,g) \ge \mathrm{err}_{\calD_p}(f^*,g^*) \ge \frac{2(1-p)}{2-p}$$

For every $i \in [n]$, we define $\beta_i \triangleq \Pr_{B}[g(B) = i]$. Since under the distribution $\mathcal{D}_p$, the subsets $A$ and $B$ are independent, we have that when Bob's strategy is fixed to $g$, the strategy of Alice that results in the largest agreement probability is given by
$$\forall A \subseteq [n], \quad f^*(A) = \argmax_{i \in A} \beta_i$$
Thus, for a permutation $\sigma$ of $[n]$ such that $\beta_{\sigma^{-1}(1)} \geq \beta_{\sigma^{-1}(2)} \geq \dots \geq \beta_{\sigma^{-1}(n)}$, we have,
\begin{equation*}
\forall A \subseteq [n], \quad f^*(A) = \argmin_{i \in A} \sigma(i).
\end{equation*}
%Thus, so far we have that, $\mathrm{err}_{\calD_p}(f,g) \ge \mathrm{err}_{\calD_p}(f^*,g)$.
Now, for every $i \in [n]$, we define $\alpha_i \triangleq \Pr_{A}[f^*(A) = i]$. When Alice's strategy is fixed to $f^*$, the strategy of Bob that results in the largest agreement probability is given by
$$\forall B \subseteq [n], \quad g^*(B) = \argmax_{i \in B} \alpha_i$$
We now claim that $\alpha_{\sigma^{-1}(1)} \geq \alpha_{\sigma^{-1}(2)} \geq \dots \geq \alpha_{\sigma^{-1}(n)}$, and hence,
$$\forall B \subseteq [n], \quad g^*(B) = \argmin_{i \in B} \sigma(i)$$
This follows easily because for each $i \in [n]$, we have that,
$$\alpha_i \ = \ \Pr_{A}\bigg[\inparen{\argmin_{\ell \in A} \sigma(\ell)} = i\bigg] \ = \ (1-p)^{i-1} \cdot p$$
Thus, we conclude that
\begin{eqnarray*}
\Pr_{(A,B) \sim \mathcal{D}_p}[f(A) = g(B)] &\le& \Pr_{(A,B) \sim \mathcal{D}_p}[f^*(A) = g(B)]\\ 
&\le& \Pr_{(A,B) \sim \mathcal{D}_p}[f^*(A) = g^*(B)]\\ 
&=& \displaystyle\sum\limits_{i=1}^n \Pr_{(A,B) \sim \mathcal{D}_p}[f^*(A) = g^*(B) = i]\\ 
&=& \displaystyle\sum\limits_{i=1}^n \Pr_{A}[f^*(A) = i] \cdot \Pr_{B}[g^*(B) = i]\\ 
&=& \displaystyle\sum\limits_{i=1}^n (1-p)^{2 \cdot (i-1)} \cdot p^2\\ 
&\le& \frac{p}{2-p},
\end{eqnarray*}
where the second equality uses the fact that under $\mathcal{D}_p$, the subsets $A$ and $B$ are independent. Thus, we obtain that,
$$\mathrm{err}_{D_p}(f,g) \ \ge \ 1 - \frac{p}{2-p} \ = \ \frac{2(1-p)}{2-p}$$
\end{proof}

\noindent We are now ready to prove our main result which is a lower bound on the error in correlated sampling.
\begin{proof}[Proof of \Cref{thm:main}]
Let $\delta \in (0,1)$ and $\gamma > 0$. Assume for the sake of contradiction that there is a correlated sampling strategy $(f^*,g^*)$ that, when run on distributions at total variation distance up to $\delta$, has error probability at most $\frac{2 \cdot \delta}{1+\delta} - \gamma$. Fix $\delta' \in (0,1)$ such that
\begin{equation}\label{eq:delta_prime}
\frac{2 \cdot \delta}{1+\delta} - \gamma < \frac{2 \cdot \delta'}{1+\delta'} < \frac{2 \cdot \delta}{1+\delta}.
\end{equation}
Note that \Cref{eq:delta_prime} implies that $\delta' < \delta$. Consider the distribution $\mathcal{D}_p$ over pairs $(A,B)$ of subsets $A,B \subseteq [n]$ where each $i \in [n]$ is independently included in each of $A$ and $B$ with probability $p \triangleq 1-\delta'$. We then have that $\Ex[|A|] = \Ex[|B|] = p \cdot n$, and $\Ex[|A \cap B|] = p^2 \cdot n$. Moreover, by the Chernoff bound, we have that
$$\Pr_{A}[||A| - p\cdot n| > p \cdot n^{0.99}] \le e^{-p \cdot n^{0.98} /2},$$
$$\Pr_{B}[||B| - p\cdot n| > p \cdot n^{0.99}] \le e^{-p \cdot n^{0.98} /2},$$
and
$$\Pr_{A,B}[||A \cap B| - p^2\cdot n| > p^2 \cdot n^{0.99}] \le e^{-p^2 \cdot n^{0.98} /2}.$$
Hence, by the union bound and since $p \le 1$, we get that with probability at least $1 - 3\cdot e^{-p^2 \cdot n^{0.98} /2}$, we have that $||A| - p\cdot n| \le p n^{0.99}$, $||B| - p\cdot n| \le p n^{0.99}$ and $||A \cap B| - p^2\cdot n| \le p^2 n^{0.99}$. Consider now the distributions $P = \mathcal{U}(A)$ (on Alice's side) and $Q = \mathcal{U}(B)$ (on Bob's side). Then, with probability at least $1 - 3\cdot e^{-p^2 \cdot n^{0.98} /2}$, it holds that,
\begin{eqnarray*}
\dTV(P,Q) &=& 1 - \frac{|A \cap B|}{\max\{|A|,|B|\}}\\ 
&\le& 1-p + o_n(1)\\ 
&=& \delta' + o_n(1)\\
&<& \delta \quad \text{for sufficiently large $n$.}
\end{eqnarray*}
%Thus, for sufficiently large $n$, we have that $\dTV(P,Q) < \delta$.
Note that, Yao's minimax principle implies that any correlated sampling strategy for $(P,Q)$ pairs with $P = \mathcal{U}(A)$ and $Q = \mathcal{U}(B)$ yields a constrained agreement strategy $(f,g)$ for the corresponding pairs $(A,B)$ of subsets. Hence, \Cref{le:prod_opt} implies that
\begin{equation}\label{eq:min_lb}
\forall \ f, g, \quad \Pr_{(A,B) \sim \mathcal{D}}[f(A) \neq g(B)] \geq \frac{2(1-p)}{2-p} = \frac{2 \cdot \delta'}{1+\delta'}
\end{equation}
where $(f,g)$ is any correlated sampling strategies. On the other hand, the property of the assumed strategy $(f^*,g^*)$ implies that
\begin{equation}\label{eq:min_ub}
\exists \ f, g, \quad \Pr_{(A,B) \sim \mathcal{D}}[f(A) \neq g(B)] \le \frac{2 \cdot \delta}{1+\delta} - \gamma + o_n(1).
\end{equation}
Putting \Cref{eq:min_lb,eq:min_ub} together contradicts \Cref{eq:delta_prime} for sufficiently large $n$.
\end{proof}

\subsection{Lower Bound in a Special Case}\label{sec:large_int_pf}
In this section, we describe the lower bound in \Cref{thm:opt_large_inter}, which is incomparable to \Cref{thm:main}.\\

\begin{proofof}{\Cref{thm:opt_large_inter}}
Let $A, B \subseteq [n]$ be such that $|A| = |B| = |A \cap B| + 1$ and let $P = \mathcal{U}(A)$ and $Q  = \mathcal{U}(B)$. Assume for the sake of contradiction that there is a correlated sampling strategy with disagreement probability $< 1 - |A \cap B|/|A \cup B| = 2/n$. Let $\mathcal{D}$ be the uniform distribution over pairs $(A,B)$ of subsets of $[n]$ satisfying $A \cup B = [n]$ and $|A| = |B| = |A \cap B| + 1$. Then, there is a deterministic strategy pair $(f,g)$ solving constrained agreement over $\mathcal{D}$ with error probability
\begin{equation}\label{eq:cont}
\Pr_{(A,B) \sim \mathcal{D}}[f(A) \neq g(B)] < \frac{2}{n}.
\end{equation}
Let
$$i \ \defeq \ \argmax_{\ell \in [n]} \bigg|\bigg\{A \in {[n] \choose n-1}: f(A)= \ell\bigg\}\bigg|$$
be the element that is most frequently output by Alice's strategy $f$, and denote its number of occurences by
$$k \ \defeq \ \bigg|\bigg\{A \in {[n] \choose n-1}: f(A)= i\bigg\}\bigg|.$$
We consider three different cases depending on the value of $k$:
\begin{enumerate}
\item[(i)] If $k \le n-3$, then consider any $B \subseteq [n]$ with $|B| = n-1$. For any value of $f(B) \in B$, the conditional error probability $\Pr[f(A) \neq g(B)\, |\, B]$ is at least $2/(n-1)$. Averaging over all such $B$, we get a contradiction to \Cref{eq:cont}.
\item[(ii)] If $k = n-2$, let $A_1 \neq A_2$ be the two subsets of $[n]$ with $|A_1| = |A_2| = n-1$ such that $f(A_1) \neq i$ and $f(A_2) \neq i$. For any $B \subseteq [n]$ with $|B| = n-1$ such that $B \neq A_1$ and $B \neq A_2$, the conditional error probability $\Pr[f(A) \neq g(B)\, |\, B]$ is at least $2/(n-1)$. Note that there are $n-2$ such $B$'s, and that either $A_1$ or $A_2$ is the set $[n] \setminus \set{i}$. If $B = [n] \setminus \set{i}$, then the conditional disagreement probability $\Pr[f(A) \neq g(B)\, |\, B]$ is at least $(n-2)/(n-1)$. Averaging over all $B$, we get that
\begin{eqnarray*}
\Pr_{(A,B) \sim \mathcal{D}}[f(A) \neq g(B)] &\geq& \bigg(\frac{2}{n-1} \bigg) \cdot \bigg(\frac{n-2}{n}\bigg) + \bigg(\frac{n-2}{n-1}\bigg) \cdot \bigg(\frac{1}{n}\bigg)\\ 
&\ge& \frac{2}{n},
\end{eqnarray*}
where the last inequality holds for any $n \geq 2$. This contradicts \Cref{eq:cont}.
\item[(iii)] If $k = n-1$, then the only subset $A_1$ of $[n]$ with $|A_1| = n-1$ and such that $f(A_1) \neq i$ is $A_1 = [n] \setminus \{i\}$. For any $B \neq A_1$, the conditional error probability $\Pr[f(A) \neq g(B)\, |\, B]$ is at least $1/(n-1)$. On the other hand, if $B = A_1$, then the conditional error probability is equal to $1$. Averaging over all $B$, we get that
\begin{eqnarray*}
\Pr_{(A,B) \sim \mathcal{D}}[f(A) \neq g(B)] &\geq& \bigg(\frac{1}{n-1} \bigg) \cdot \bigg( \frac{n-1}{n} \bigg) + 1 \cdot \bigg(\frac{1}{n} \bigg)\\ 
&=& \frac{2}{n},
\end{eqnarray*}
which contradicts \Cref{eq:cont}.
\end{enumerate}
\end{proofof}
protocols.tex
\section{Correlated Sampling Strategies}\label{sec:protocols}

In this section, we describe the correlated sampling strategy that proves \Cref{thm:Holest}. First, let's consider the case of {\em flat distributions} where, the distributions $P$ and $Q$ are promised to be of the following form, that there exist $A, B \subseteq [n]$ such that $P = \mathcal{U}(A)$ and $Q  = \mathcal{U}(B)$ over the universe $[n]$. In this case, it is easy to show that the protocol given in Algorithm~\ref{prot:minhash} achieves an error probability of $1 - \frac{|A \cap B|}{|A \cup B|}$. Since $\pi$ is a random permutation, it is clear that $f(A,\pi)$ is uniformly distributed over $A$ and $g(B, \pi)$ is uniformly distributed over $B$. Let $i_0$ be the smallest index such that $\pi(i_0) \in A\cup B$. The probability that $\pi(i_0) \in A \cap B$ is exactly $\frac{|A \cap B|}{|A \cup B|}$, and this happens precisely when $f(A,\pi) = g(B,\pi)$. Hence, we get the claimed error probability.

\begin{algorithm}[tp]
	{\bf Alice's input:} $A \subseteq [n]$\\
	{\bf Bob's input:} $B \subseteq [n]$\\
	{\bf Shared randomness:} a random permutation $\pi : [n] \to [n]$\\
	\vspace{2mm}
	{\bf Strategy:}
	\begin{itemize}
		\item $f(A,\pi) = \pi(i_A)$, where $i_A$ is the smallest index such that $\pi(i_A) \in A$.
		\item $g(B,\pi) = \pi(i_B)$, where $i_B$ is the smallest index such that $\pi(i_B) \in B$.
	\end{itemize}
	\caption{MinHash strategy \cite{broder1997resemblance}} \label{prot:minhash}
\end{algorithm}

The strategy desired in Theorem~\ref{thm:Holest} can now be obtained by a reduction to the case of {\em flat} distributions, and subsequently using the MinHash strategy.\\

\begin{proofof}{\Cref{thm:Holest}}
	Given a universe $\Omega$, define a new universe $\Omega' = \Omega \times \Gamma$, where $\Gamma = \set{0, \gamma, 2\gamma, \cdots, 1}$ for a sufficiently small value of $\gamma > 0$. Thus, $|\Omega'| = \frac{1}{\gamma} \cdot |\Omega|$. Suppose we are given distributions $P$ and $Q$ such that $\dTV(P,Q) = \delta$. Define $A = \setdef{(\omega, p) \in \Omega \times \Gamma}{p < P(\omega)}$ and $B = \setdef{(\omega, q) \in \Omega \times \Gamma}{q < Q(\omega)}$.
	
	Holenstein's strategy can now be simply described as follows: Alice and Bob use the MinHash strategy on inputs $A$ and $B$ over the universe $\Omega'$, to obtain elements $(\omega_A, p_A)$ and $(\omega_B, p_B)$ respectively, and they simply output $\omega_A$ and $\omega_B$ respectively. This strategy is summarized in Algorithm~\ref{prot:holenstein}.\\
	
	\noindent It can easily seen that,
	$|A| = \sum_{\omega \in \Omega} \floor{\frac{P(\omega)}{\gamma}}$ and hence,
	$$\sum_{\omega \in \Omega} \inparen{\frac{P(\omega)}{\gamma} - 1} \le |A| \le \sum_{\omega \in \Omega} \frac{P(\omega)}{\gamma}$$
	And hence,
	$$\frac{1}{\gamma} - |\Omega| \le |A|, |B| \le \frac{1}{\gamma}$$
	Similarly, $|A \cap B| = \sum_{\omega \in \Omega} \min\set{\floor{\frac{P(\omega)}{\gamma}}, \floor{\frac{Q(\omega)}{\gamma}}}$ and $|A \cup B| = \sum_{\omega \in \Omega} \max\set{\floor{\frac{P(\omega)}{\gamma}}, \floor{\frac{Q(\omega)}{\gamma}}}$ and hence,
	$$\frac{1-\delta}{\gamma} - |\Omega| \ \le \ |A \cap B| \ \le \ \frac{1-\delta}{\gamma}$$
	$$\frac{1+\delta}{\gamma} - |\Omega| \ \le \ |A \cup B| \ \le \ \frac{1+\delta}{\gamma}$$
	
	\noindent The probability that Alice outputs $\omega_A$ is $\frac{\floor{\frac{P(\omega_A)}{\gamma}}}{|A|}$, which is bounded as,
	$$P(\omega_A) - \gamma \le \frac{\floor{\frac{P(\omega_A)}{\gamma}}}{|A|} \le \frac{P(\omega_A)}{1-\gamma \cdot |\Omega|}$$
	Thus, it follows that as $\gamma \to 0$, Alice's output is distributed according to $P$, and similarly Bob's output is distributed according to $Q$. Moreover, we have that,
	$$\Pr[\omega_A \ne \omega_B] \ = \ 1 - \frac{|A \cap B|}{|A \cup B|} \ \le \ 1 - \frac{1-\delta - \gamma \cdot |\Omega|}{1+\delta} \ = \ \frac{2 \delta + \gamma \cdot |\Omega|}{1+\delta} \to \frac{2 \delta}{1+\delta}$$
	This gives us the desired error probability.
\end{proofof}

\begin{algorithm}[tp]
	{\bf Alice's input:} $P \in \Delta_\Omega$\\
	{\bf Bob's input:} $Q \in \Delta_\Omega$\\
	{\bf Pre-processing:} Let $\Omega' = \Omega \times \Gamma$, where $\Gamma = \set{0, \gamma, 2\gamma, \cdots, 1}$ (for suitable $\gamma > 0$)\\
	{\bf Shared randomness:} $r \sim \calR$ as required by the MinHash strategy on $\Omega'$\\
	\vspace{2mm}
	{\bf Strategy:}
	\begin{itemize}
		\item Let $A = \setdef{(\omega, p) \in \Omega \times \Gamma}{p < P(\omega)}$ and $B = \setdef{(\omega, q) \in \Omega \times \Gamma}{q < Q(\omega)}$.
		\item Alice and Bob use MinHash strategy (Algorithm~\ref{prot:minhash}) with inputs $A$, $B$ on universe $\Omega'$\\
		to obtain $(\omega_A, p_A)$ and $(\omega_B, p_B)$ respectively.
		\item Alice outputs $\omega_A$.
		\item Bob outputs $\omega_B$.
	\end{itemize}
	\caption{Holenstein's strategy \cite{holenstein2007parallel}} \label{prot:holenstein}
\end{algorithm}

\subsection{Strategy in a Special Case}\label{sec:special_protocols}

In this section, we describe the correlated sampling strategy of \cite{Rivest} that proves \Cref{thm:rivest}. To do so, we will need the well-known Hall's Theorem.

\begin{theorem}[Hall; \cite{van2001course}]\label{th:hall}
Consider a bipartite graph $G$ on vertex sets $L$ and $R$. Then, there is a matching that entirely covers $L$ if and only if for every subset $S \subseteq L$, we have that $|S| \le |N_G(S)|$, where $N_G(S)$ denotes the set of all neighbors of elements of $S$ in $G$.
\end{theorem}

\begin{proofof}{\Cref{thm:rivest}}
	Alice and Bob have subsets $A, B \subseteq [n]$ respectively such that $|A| = |B| = k$, $|A \cap B| = 1$ and $A \cup B = [n]$. This forces $n = 2k-1$. Consider the bipartite graph $G$ on vertices $\binom{[n]}{k} \times \binom{[n]}{k}$, with an edge between vertices $A$ and $B$ if $|A \cap B| = 1$. It is easy to see that $G$ is $k$-regular. Iteratively using Hall's theorem (\Cref{th:hall}), we get that the edges of $G$ can be written as a disjoint union of $k$ matchings. Let's denote these as $M_1, M_2, \cdots, M_k$.
	
	The strategy of Alice and Bob is as follows: Use the shared randomness to sample a random index $r \in [k]$ and consider the matching $M_r$. If $(A,B')$ is the edge present in $M_r$, then Alice outputs the unique element in $A \cap B'$. Similarly, if $(A',B)$ is the edge present in $M_r$, then Bob outputs the unique element in $A' \cap B$. This protocol is summarized in Algorithm~\ref{prot:rivest}.
	
	It is easy to see that both Alice and Bob are outputting uniformly random elements in $A$ and $B$ respectively. Moreover, the probability that they output the same element, is exactly $1/k$, which is the probability of choosing the unique matching $M_r$ which contains the edge $(A,B)$ (i.e. enforcing $A = A'$ and $B = B'$).
\end{proofof}

\begin{algorithm}[tp]
	{\bf Alice's input:} $A \subseteq [n]$\\
	{\bf Bob's input:} $B \subseteq [n]$\\
	{\bf Promise:} $|A| = |B| = k$, $|A \cap B| = 1$ and $A \cup B = [n]$\\
	{\bf Pre-processing:} Let $G$ be the bipartite graph on vertices $\binom{[n]}{k} \times \binom{[n]}{k}$, with an edge between vertices $A$ and $B$ if $|A \cap B| = 1$. Decompose the edges of $G$ into $k$ disjoint matchings $M_1, \cdots, M_k$.\\
	{\bf Shared randomness:} Index $r \in [k]$\\
	\vspace{2mm}
	{\bf Strategy:}
	\begin{itemize}
		\item Let $(A,B')$ and $(A', B)$ be edges present in $M_r$.
		\item Alice outputs the unique element in $A \cap B'$.
		\item Bob outputs the unique element in $A' \cap B$.
	\end{itemize}
	\caption{Rivest's strategy \cite{Rivest}} \label{prot:rivest}
\end{algorithm}


references.bbl
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{BHH{\etalchar{+}}08}

\bibitem[BHH{\etalchar{+}}08]{barak2008rounding}
Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, and David Steurer.
\newblock Rounding parallel repetitions of unique games.
\newblock In {\em Foundations of Computer Science, 2008. FOCS'08. IEEE 49th
  Annual IEEE Symposium on}, pages 374--383. IEEE, 2008.

\bibitem[Bro97]{broder1997resemblance}
Andrei~Z Broder.
\newblock On the resemblance and containment of documents.
\newblock In {\em Compression and Complexity of Sequences 1997. Proceedings},
  pages 21--29. IEEE, 1997.

\bibitem[Cha02]{charikar2002similarity}
Moses~S Charikar.
\newblock Similarity estimation techniques from rounding algorithms.
\newblock In {\em Proceedings of the thiry-fourth annual ACM symposium on
  Theory of computing}, pages 380--388. ACM, 2002.

\bibitem[GP06]{gollapudi2006dictionary}
Sreenivas Gollapudi and Rina Panigrahy.
\newblock A dictionary for approximate string search and longest prefix search.
\newblock In {\em Proceedings of the 15th ACM international conference on
  Information and knowledge management}, pages 768--775. ACM, 2006.

\bibitem[Hol07]{holenstein2007parallel}
Thomas Holenstein.
\newblock Parallel repetition: simplifications and the no-signaling case.
\newblock In {\em Proceedings of the thirty-ninth annual ACM symposium on
  Theory of computing}, pages 411--419. ACM, 2007.

\bibitem[KT02]{kleinberg2002approximation}
Jon Kleinberg and Eva Tardos.
\newblock Approximation algorithms for classification problems with pairwise
  relationships: Metric labeling and markov random fields.
\newblock {\em Journal of the ACM (JACM)}, 49(5):616--639, 2002.

\bibitem[M{\etalchar{+}}94]{manber1994finding}
Udi Manber et~al.
\newblock Finding similar files in a large file system.
\newblock In {\em Usenix Winter}, volume~94, pages 1--10, 1994.

\bibitem[MMT10]{manasse2010consistent}
Mark Manasse, Frank McSherry, and Kunal Talwar.
\newblock Consistent weighted sampling.
\newblock {\em Unpublished technical report) http://research. microsoft.
  com/en-us/people/manasse}, 2010.

\bibitem[Rao11]{rao2011parallel}
Anup Rao.
\newblock Parallel repetition in projection games and a concentration bound.
\newblock {\em SIAM Journal on Computing}, 40(6):1871--1891, 2011.

\bibitem[Riv16]{Rivest}
Ronald~L. Rivest.
\newblock Symmetric encryption via keyrings and ecc.
\newblock \url{http://arcticcrypt.b.uib.no/files/2016/07/Slides-Rivest.pdf},
  2016.

\bibitem[vLW01]{van2001course}
Jacobus~Hendricus van Lint and Richard~Michael Wilson.
\newblock {\em A course in combinatorics}.
\newblock Cambridge university press, 2001.

\end{thebibliography}
