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 #1 to TR12-070 | 17th April 2014 21:01

The Complexity of Estimating Min-Entropy

RSS-Feed




Revision #1
Authors: Thomas Watson
Accepted on: 17th April 2014 21:01
Downloads: 488
Keywords: 


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).


Paper:

TR12-070 | 26th May 2012 04:54

The Complexity of Estimating Min-Entropy





TR12-070
Authors: Thomas Watson
Publication: 26th May 2012 12:37
Downloads: 1451
Keywords: 


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).



ISSN 1433-8092 | Imprint