Problem 87: Equivalence Testing with Conditional Samples

Suggested by	Gautam Kamath
Source	FOCS 2017
Short link	https://sublinear.info/87

This is a continuation of this previous open problem from the Bertinoro workshop Bertinoro Workshop on Sublinear Algorithms.

For constant $\varepsilon>0$ it is known that the sample complexity of equivalence testing, in the conditional oracle model where the algorithm gets to condition the samples it receives on arbitrary subsets of the domain $[n]$, is $\Omega(\sqrt{\log\log n})$ and $O({\log\log n})$. [AcharyaCK-14,FalahatgarJOPS-15].

What is the exact dependence on the domain size of the sample complexity of equivalence testing in the conditional oracle model?