Difference between revisions of "Open Problems:86"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (Krzysztof Onak moved page Waiting:Equivalence testing lower bound via communication complexity to Open Problems:86 without leaving a redirect)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Equivalence testing lower bound via communication complexity
 
 
|source=focs17
 
|source=focs17
 
|who=Clément Canonne
 
|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 “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 [[Open_Problems:83|Problem 83]]).
  
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, for some meaningful notion of “instance-specific?”

Latest revision as of 15:56, 8 November 2017

Suggested by Clément Canonne
Source FOCS 2017
Short link https://sublinear.info/86

Blais, Canonne, and Gur [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 [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 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 [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?”