Difference between revisions of "Open Problems:87"
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
|source=focs17 | |source=focs17 | ||
| − | |who= | + | |who=Jayadev Acharya |
| − | |||
}} | }} | ||
| + | (This is a continuation of [[Open_Problems:66|Problem 66]] from the [[Workshops:Bertinoro_2014|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})$ {{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})$ | ||
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? | ||
Latest revision as of 16:05, 8 November 2017
| 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?
