Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR16-015 | 24th March 2016 15:54

The uniform distribution is complete with respect to testing identity to a fixed distribution

RSS-Feed




Revision #3
Authors: Oded Goldreich
Accepted on: 24th March 2016 15:54
Downloads: 248
Keywords: 


Abstract:

Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whether an unknown distribution over $[n]$ equals a fixed distribution to this very problem when the fixed distribution is uniform over $[n]$. Our reduction preserves the parameters of the problem, which are $n$ and the proximity parameter $\e>0$, up to a constant factor.

While this reduction yields no new bounds on the sample complexity of either problems, it provides a simple way of obtaining testers for equality to arbitrary fixed distributions from testers for the uniform distribution.



Changes to previous version:

This version contains an appendix detailing a comment that appears right after Cor 13.


Revision #2 to TR16-015 | 10th February 2016 11:22

The uniform distribution is complete with respect to testing identity to a fixed distribution





Revision #2
Authors: Oded Goldreich
Accepted on: 10th February 2016 11:22
Downloads: 311
Keywords: 


Abstract:

Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whether an unknown distribution over $[n]$ equals a fixed distribution to this very problem when the fixed distribution is uniform over $[n]$. Our reduction preserves the parameters of the problem, which are $n$ and the proximity parameter $\e>0$, up to a constant factor.

While this reduction yields no new bounds on the sample complexity of either problems, it provides a simple way of obtaining testers for equality to arbitrary fixed distributions from testers for the uniform distribution.



Changes to previous version:

Haste has caused an error in my claims regarding the open problems posed originally in Section 4. These are only partially addressed by the current results.


Revision #1 to TR16-015 | 8th February 2016 16:28

The uniform distribution is complete with respect to testing identity to a fixed distribution





Revision #1
Authors: Oded Goldreich
Accepted on: 8th February 2016 16:28
Downloads: 307
Keywords: 


Abstract:

Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whether an unknown distribution over $[n]$ equals a fixed distribution to this very problem when the fixed distribution is uniform over $[n]$. Our reduction preserves the parameters of the problem, which are $n$ and the proximity parameter $\e>0$, up to a constant factor.

While this reduction yields no new bounds on the sample complexity of either problems, it provides a simple way of obtaining testers for equality to arbitrary fixed distributions from testers for the uniform distribution.



Changes to previous version:

The open problems stated in prior version are easy to resolve, to a large extent, using the results of Valiant and Valiant (2011). Details are provided in the revised Sec 4. In addition, some typos were fixed and some clarification were made.


Paper:

TR16-015 | 4th February 2016 22:26

The uniform distribution is complete with respect to testing identity to a fixed distribution





TR16-015
Authors: Oded Goldreich
Publication: 4th February 2016 22:26
Downloads: 777
Keywords: 


Abstract:

Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whether an unknown distribution over $[n]$ equals a fixed distribution to this very problem when the fixed distribution is uniform over $[n]$. Our reduction preserves the parameters of the problem, which are $n$ and the proximity parameter $\e>0$, up to a constant factor.

While this reduction yields no new bounds on the sample complexity of either problems, it provides a simple way of obtaining testers for equality to arbitrary fixed distributions from testers for the uniform distribution.



ISSN 1433-8092 | Imprint