Open Problems:87 - Revision history

Krzysztof Onak at 16:05, 8 November 2017

2017-11-08T16:05:26Z

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

2017-11-08T16:03:30Z

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

Krzysztof Onak: Cleaning the header, small changes

2017-11-08T16:03:09Z

Cleaning the header, small changes

Ccanonne at 23:24, 25 October 2017

2017-10-25T23:24:17Z

Ccanonne at 22:57, 25 October 2017

2017-10-25T22:57:57Z

Ccanonne: Created page with "{{Header |source=focs17 |who=Gautam Kamath |title=Equivalence testing with conditional samples }} ''This is a continuation of this previous open problem..."

2017-10-25T22:57:18Z

Created page with "{{Header |source=focs17 |who=Gautam Kamath |title=Equivalence testing with conditional samples }} ''This is a continuation of this previous open problem..."

New page

{{Header
|source=focs17
|who=Gautam Kamath
|title=Equivalence testing with conditional samples
}}

''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}}.

What is the exact dependence on the domain size of the sample complexity of equivalence testing in the conditional oracle model?

@@ Line 3: / Line 3: @@
 |who=Jayadev Acharya
 }}
-(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|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}}.
 What is the exact dependence on the domain size of the sample complexity of equivalence testing in the conditional oracle model?

@@ Line 2: / Line 2: @@
 |source=focs17
 |who=Jayadev Acharya
 }}
-''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}}.
 What is the exact dependence on the domain size of the sample complexity of equivalence testing in the conditional oracle model?

← Older revision	Revision as of 16:03, 8 November 2017
(No difference)

@@ Line 1: / Line 1: @@
 {{Header
 |source=focs17
-|who=Gautam Kamath
+|who=Jayadev Acharya
 |title=Equivalence testing with conditional samples
 }}

@@ 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}}.
 What is the exact dependence on the domain size of the sample complexity of equivalence testing in the conditional oracle model?