Difference between revisions of "Open Problems:87"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(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||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 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?