Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error

2021-07-25-MD-Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error

paper

Results

• I am only going to cover the convertion between public coin protocols to private coin protocols.
• This is an improvement over the original Newman's Theorem.
• Theorem (Neumann): $R_{\epsilon +\delta}^{priv}(F) \leq R_\epsilon^{pub}(F) + \log n/\delta^2 + O(1)$.
• Result: $\forall \epsilon,\delta$ in sufficient ranges $R_{\epsilon (1 +\delta)}^{priv}(F) \leq R_\epsilon^{pub}(F) + \log n/\epsilon + \log 6/\delta^2$.
  • This follows similar to Neumann but uses a multiplicative Chernoff bound instead of an additive one.
  • This seems like a good way to get familiar with this proof.

Proof

• Let $\Pi$ be a protocol that computes $F$ with error $\epsilon$.
• Set $B=6n/\delta^2\epsilon$.
• Independently choose random strings $r_1,\dots,r_B$ according to the distribution used by $\Pi$.
• Let $I_{j,x,y}$ denote the indicator that $r_j$ is a bad random string for $x,y$.
• Fix two arbitrary inputs $x,y$. The error probability implies that $\Pr_{r_1,\dots,r_B}[I_{j,x,y}=1] \leq \epsilon$.
• Linearity of expecation now gives $E_{r_1,\dots,r_B}[\sum_{j\in B}I_{j,x,y}]\leq B\epsilon =6n/\delta^2$.
• Now we give an upper bound on $\Pr_{r_1,\dots,r_B}[\sum_{j\in B}I_{j,x,y} \geq B\epsilon(1+\delta)]$.
• This can be bounded by Chernoff with $\leq \exp(-\delta^2 6n/3\delta^2)=\exp(-2n) < 2^{-2n}$.
• Now we union bound over all $x,y$ giving us $Pr[\text{the sum is above B\epsilon(1+\delta) for some x,y}]\leq \sum_{x,y} Pr[...]$
• This is bounded by $2^{2n} 2^{-2n}=1$.
• Hence, there exists a choice of $r_1,\dots,r_B$ that gives the protocol random private coin bits.