__
Revision #1 to TR12-070 | 17th April 2014 21:01
__
#### The Complexity of Estimating Min-Entropy

**Abstract:**
Goldreich, 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).

__
TR12-070 | 26th May 2012 04:54
__

#### The Complexity of Estimating Min-Entropy

**Abstract:**
Goldreich, 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).