Difference between revisions of "Open Problems:87"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (Cleaning the header, small changes)
Line 2: Line 2:
 
|source=focs17
 
|source=focs17
 
|who=Jayadev Acharya
 
|who=Jayadev Acharya
|title=Equivalence testing with conditional samples
 
 
}}
 
}}
 +
(This is a continuation of [[Open_Problems:66|Problem 66]] from the [[Workshops:Bertinoro_2014|Bertinoro]] workshop Bertinoro Workshop on Sublinear Algorithms.)
  
''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 16:03, 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 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?