# Difference between revisions of "Open Problems:87"

m (Krzysztof Onak moved page Waiting:Equivalence testing with conditional samples to Open Problems:87 without leaving a redirect) |
|||

Line 3: | Line 3: | ||

|who=Jayadev Acharya | |who=Jayadev Acharya | ||

}} | }} | ||

− | (This is a continuation of [[Open_Problems:66|Problem 66]] from the [[Workshops:Bertinoro_2014| | + | (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})$ {{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? |

## 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?