Difference between revisions of "Open Problems:86"
(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...") |
|||
| 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 | + | 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? |
Revision as of 22:07, 25 October 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 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?
