Editing Open Problems:87

{{Header
|source=focs17
|who=Gautam Kamath
|title=Equivalence testing with conditional samples
}}

''This is a continuation of [[Open_Problems:66|this previous open problem]] from the [[Workshops:Bertinoro_2014||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})$. {{cite|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?