期刊名称:Electronic Colloquium on Computational Complexity
印刷版ISSN:1433-8092
出版年度:2012
卷号:2012
出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要: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).