Difference between revisions of "Open Problems:87"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
 
|source=focs17
 
|source=focs17
|who=Gautam Kamath
+
|who=Jayadev Acharya
|title=Equivalence testing with conditional samples
 
 
}}
 
}}
 +
(This is a continuation of [[Open_Problems:66|Problem 66]] from the [[Workshops:Bertinoro_2014|2014 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?

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?