Problem 87: Equivalence Testing with Conditional Samples

From Open Problems in Sublinear Algorithms
Revision as of 16:05, 8 November 2017 by Krzysztof Onak (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Suggested by Jayadev Acharya
Source FOCS 2017
Short link https://sublinear.info/87

(This is a continuation of Problem 66 from the 2014 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?