Difference between revisions of "Open Problems:87"
(Created page with "{{Header |source=focs17 |who=Gautam Kamath |title=Equivalence testing with conditional samples }} ''This is a continuation of this previous open problem...") |
|||
| Line 5: | Line 5: | ||
}} | }} | ||
| − | ''This is a continuation of [[Open_Problems:66|this previous open problem]] from the [[Workshops:Bertinoro_2014 | + | ''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}}. | 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? | What is the exact dependence on the domain size of the sample complexity of equivalence testing in the conditional oracle model? | ||
Revision as of 22:57, 25 October 2017
| 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?
