ECCC-Report TR16-015https://eccc.weizmann.ac.il/report/2016/015Comments and Revisions published for TR16-015en-usThu, 24 Mar 2016 15:54:23 +0200
Revision 3
| The uniform distribution is complete with respect to testing identity to a fixed distribution |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/015#revision3Inspired 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.
Thu, 24 Mar 2016 15:54:23 +0200https://eccc.weizmann.ac.il/report/2016/015#revision3
Revision 2
| The uniform distribution is complete with respect to testing identity to a fixed distribution |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/015#revision2Inspired 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.
Wed, 10 Feb 2016 11:22:18 +0200https://eccc.weizmann.ac.il/report/2016/015#revision2
Revision 1
| The uniform distribution is complete with respect to testing identity to a fixed distribution |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/015#revision1Inspired 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.
Mon, 08 Feb 2016 16:28:20 +0200https://eccc.weizmann.ac.il/report/2016/015#revision1
Paper TR16-015
| The uniform distribution is complete with respect to testing identity to a fixed distribution |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/015Inspired 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.
Thu, 04 Feb 2016 22:26:58 +0200https://eccc.weizmann.ac.il/report/2016/015