Open Problems:86 - Revision history

Krzysztof Onak: Krzysztof Onak moved page Waiting:Equivalence testing lower bound via communication complexity to Open Problems:86 without leaving a redirect

2017-11-08T15:56:57Z

Krzysztof Onak moved page Waiting:Equivalence testing lower bound via communication complexity to Open Problems:86 without leaving a redirect

Krzysztof Onak: Cleaning the header, small changes

2017-11-08T15:56:25Z

Cleaning the header, small changes

Ccanonne at 22:09, 25 October 2017

2017-10-25T22:09:51Z

Ccanonne at 22:09, 25 October 2017

2017-10-25T22:09:23Z

Ccanonne at 22:07, 25 October 2017

2017-10-25T22:07:19Z

Ccanonne: Created page with "{{Header |title=Equivalence testing lower bound via communication complexity |source=focs17 |who=Clément Canonne }} Blais, Canonne, and Gur {{cite|BlaisCG-17}} recently descr..."

2017-10-25T22:07:05Z

Created page with "{{Header |title=Equivalence testing lower bound via communication complexity |source=focs17 |who=Clément Canonne }} Blais, Canonne, and Gur {{cite|BlaisCG-17}} recently descr..."

New page

{{Header
|title=Equivalence testing lower bound via communication complexity
|source=focs17
|who=Clément Canonne
}}
Blais, Canonne, and Gur {{cite|BlaisCG-17}} recently described a reduction technique to obtain distribution testing lower bounds from communication complexity (specifically, even from the simultaneous message-passing (SMP) setting in communication complexity). Using this technique, which is the analogue of the "usual property testing" framework of Blais, Brody, and Matulef {{cite|BlaisBM-12}}, they prove and (re)-derive lower bounds for many of the standard distribution testing questions, including ''identity testing'' (and ''instance-specific'' identity testing — see [[Instance-specific Hellinger testing|this other open problem]]).

Can one use this framework to re-establish an $\tilde{\Omega}}(n^{2/3})$ sample complexity lower bound for ''equivalence'' testing (a.k.a. closeness testing; where now both distributions are unknown, instead of one known and one unknown, available through sample access)? If so, can it yield some sort of ''instance-specific'' equivalence testing lower bound?

@@ Line 1: / Line 1: @@
 {{Header
 |source=focs17
 |who=Clément Canonne
 }}
-Blais, Canonne, and Gur {{cite|BlaisCG-17}} recently described a reduction technique to obtain distribution testing lower bounds from communication complexity (specifically, even from the simultaneous message-passing (SMP) setting in communication complexity). Using this technique, which is the analogue of the "usual property testing" framework of Blais, Brody, and Matulef {{cite|BlaisBM-12}}, they prove and (re)-derive lower bounds for many of the standard distribution testing questions, including ''identity testing'' (and ''instance-specific'' identity testing — see [[Instance-specific Hellinger testing|this other open problem]]).
+Blais, Canonne, and Gur {{cite|BlaisCG-17}} recently described a reduction technique to obtain distribution testing lower bounds from communication complexity (specifically, even from the simultaneous message-passing (SMP) setting in communication complexity). Using this technique, which is the analogue of the &ldquo;usual property testing&rdquo; framework of Blais, Brody, and Matulef {{cite|BlaisBM-12}}, they prove and re-derive lower bounds for many of the standard distribution testing questions, including ''identity testing'' (and ''instance-specific'' identity testing — see [[Open_Problems:83|Problem 83]]).
 Recall that the ''equivalence'' testing problem (also known as closeness testing) is the generalization of identity testing where, instead of having a known reference distribution $q$ and access to samples from an unknown $p$, now both distributions are unknown and only available via samples.
-Can one use the {{cite|BlaisCG-17}} framework to re-establish an $\tilde{\Omega}(n^{2/3})$ sample complexity lower bound for equivalence testing? If so, can it yield some sort of ''instance-specific'' equivalence testing lower bound, for some meaningful notion of "instance-specific"?
+Can one use the {{cite|BlaisCG-17}} framework to re-establish an $\tilde{\Omega}(n^{2/3})$ sample complexity lower bound for equivalence testing? If so, can it yield some sort of ''instance-specific'' equivalence testing lower bound, for some meaningful notion of &ldquo;instance-specific?&rdquo;

← Older revision		Revision as of 22:09, 25 October 2017
Line 8:		Line 8:
	Recall that the ''equivalence'' testing problem (also known as closeness testing) is the generalization of identity testing where, instead of having a known reference distribution $q$ and access to samples from an unknown $p$, now both distributions are unknown and only available via samples.		Recall that the ''equivalence'' testing problem (also known as closeness testing) is the generalization of identity testing where, instead of having a known reference distribution $q$ and access to samples from an unknown $p$, now both distributions are unknown and only available via samples.

−	Can one use the {{cite\|BlaisCG-17}} framework to re-establish an $\tilde{\Omega}(n^{2/3})$ sample complexity lower bound for ''equivalence'' testing? If so, can it yield some sort of ''instance-specific'' equivalence testing lower bound?	+	Can one use the {{cite\|BlaisCG-17}} framework to re-establish an $\tilde{\Omega}(n^{2/3})$ sample complexity lower bound for equivalence testing? If so, can it yield some sort of ''instance-specific'' equivalence testing lower bound, for some meaningful notion of "instance-specific"?

← Older revision		Revision as of 22:09, 25 October 2017
Line 6:		Line 6:
	Blais, Canonne, and Gur {{cite\|BlaisCG-17}} recently described a reduction technique to obtain distribution testing lower bounds from communication complexity (specifically, even from the simultaneous message-passing (SMP) setting in communication complexity). Using this technique, which is the analogue of the "usual property testing" framework of Blais, Brody, and Matulef {{cite\|BlaisBM-12}}, they prove and (re)-derive lower bounds for many of the standard distribution testing questions, including ''identity testing'' (and ''instance-specific'' identity testing — see [[Instance-specific Hellinger testing\|this other open problem]]).		Blais, Canonne, and Gur {{cite\|BlaisCG-17}} recently described a reduction technique to obtain distribution testing lower bounds from communication complexity (specifically, even from the simultaneous message-passing (SMP) setting in communication complexity). Using this technique, which is the analogue of the "usual property testing" framework of Blais, Brody, and Matulef {{cite\|BlaisBM-12}}, they prove and (re)-derive lower bounds for many of the standard distribution testing questions, including ''identity testing'' (and ''instance-specific'' identity testing — see [[Instance-specific Hellinger testing\|this other open problem]]).

−	Can one use ~~this~~ framework to re-establish an $\tilde{\Omega}(n^{2/3})$ sample complexity lower bound for ''equivalence'' testing ~~(a.k.a. closeness testing; where now both distributions are unknown, instead of one known and one unknown, available through sample access)~~? If so, can it yield some sort of ''instance-specific'' equivalence testing lower bound?	+	Recall that the ''equivalence'' testing problem (also known as closeness testing) is the generalization of identity testing where, instead of having a known reference distribution $q$ and access to samples from an unknown $p$, now both distributions are unknown and only available via samples.
		+
		+	Can one use the {{cite\|BlaisCG-17}} framework to re-establish an $\tilde{\Omega}(n^{2/3})$ sample complexity lower bound for ''equivalence'' testing? If so, can it yield some sort of ''instance-specific'' equivalence testing lower bound?

← Older revision		Revision as of 22:07, 25 October 2017
Line 6:		Line 6:
	Blais, Canonne, and Gur {{cite\|BlaisCG-17}} recently described a reduction technique to obtain distribution testing lower bounds from communication complexity (specifically, even from the simultaneous message-passing (SMP) setting in communication complexity). Using this technique, which is the analogue of the "usual property testing" framework of Blais, Brody, and Matulef {{cite\|BlaisBM-12}}, they prove and (re)-derive lower bounds for many of the standard distribution testing questions, including ''identity testing'' (and ''instance-specific'' identity testing — see [[Instance-specific Hellinger testing\|this other open problem]]).		Blais, Canonne, and Gur {{cite\|BlaisCG-17}} recently described a reduction technique to obtain distribution testing lower bounds from communication complexity (specifically, even from the simultaneous message-passing (SMP) setting in communication complexity). Using this technique, which is the analogue of the "usual property testing" framework of Blais, Brody, and Matulef {{cite\|BlaisBM-12}}, they prove and (re)-derive lower bounds for many of the standard distribution testing questions, including ''identity testing'' (and ''instance-specific'' identity testing — see [[Instance-specific Hellinger testing\|this other open problem]]).

−	Can one use this framework to re-establish an $\tilde{\Omega}}(n^{2/3})$ sample complexity lower bound for ''equivalence'' testing (a.k.a. closeness testing; where now both distributions are unknown, instead of one known and one unknown, available through sample access)? If so, can it yield some sort of ''instance-specific'' equivalence testing lower bound?	+	Can one use this framework to re-establish an $\tilde{\Omega}(n^{2/3})$ sample complexity lower bound for ''equivalence'' testing (a.k.a. closeness testing; where now both distributions are unknown, instead of one known and one unknown, available through sample access)? If so, can it yield some sort of ''instance-specific'' equivalence testing lower bound?

← Older revision	Revision as of 15:56, 8 November 2017
(No difference)