ECCC-Report TR12-070https://eccc.weizmann.ac.il/report/2012/070Comments and Revisions published for TR12-070en-usThu, 17 Apr 2014 21:01:13 +0300
Revision 1
| The Complexity of Estimating Min-Entropy |
Thomas Watson
https://eccc.weizmann.ac.il/report/2012/070#revision1Goldreich, Sahai, and Vadhan (CRYPTO 1999) proved that the promise problem for estimating the Shannon entropy of a distribution sampled by a given circuit is NISZK-complete. We consider the analogous problem for estimating the min-entropy and prove that it is SBP-complete, where SBP is the class of promise problems that correspond to approximate counting of NP witnesses. The result holds even when the sampling circuits are restricted to be 3-local. For logarithmic-space samplers, we observe that this problem is NP-complete by a result of Lyngs{\o} and Pedersen on hidden Markov models (JCSS 2002).Thu, 17 Apr 2014 21:01:13 +0300https://eccc.weizmann.ac.il/report/2012/070#revision1
Paper TR12-070
| The Complexity of Estimating Min-Entropy |
Thomas Watson
https://eccc.weizmann.ac.il/report/2012/070Goldreich, Sahai, and Vadhan (CRYPTO 1999) proved that the promise problem for estimating the Shannon entropy of a distribution sampled by a given circuit is NISZK-complete. We consider the analogous problem for estimating the min-entropy and prove that it is SBP-complete, even when restricted to 3-local samplers. For logarithmic-space samplers, we observe that this problem is NP-complete by a result of Lyngs{\o} and Pedersen on hidden Markov models (JCSS 2002).Sat, 26 May 2012 12:37:21 +0300https://eccc.weizmann.ac.il/report/2012/070