# Problem 86: Equivalence Testing Lower Bound via Communication Complexity

Suggested by | Clément Canonne |
---|---|

Source | FOCS 2017 |

Short link | https://sublinear.info/86 |

Blais, Canonne, and Gur [BlaisCG-17] recently described a reduction technique to obtain distribution testing lower bounds from communication complexity (specifically, even from the simultaneous message-passing (SMP) setting in communication complexity). Using this technique, which is the analogue of the “usual property testing” framework of Blais, Brody, and Matulef [BlaisBM-12], they prove and re-derive lower bounds for many of the standard distribution testing questions, including *identity testing* (and *instance-specific* identity testing — see Problem 83).

Recall that the *equivalence* testing problem (also known as closeness testing) is the generalization of identity testing where, instead of having a known reference distribution $q$ and access to samples from an unknown $p$, now both distributions are unknown and only available via samples.

Can one use the [BlaisCG-17] framework to re-establish an $\tilde{\Omega}(n^{2/3})$ sample complexity lower bound for equivalence testing? If so, can it yield some sort of *instance-specific* equivalence testing lower bound, for some meaningful notion of “instance-specific?”