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)
 
(2 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]]).
  
 
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?”

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?”