Abstract
Goldreich et al. (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ø and Pedersen on hidden Markov models (JCSS 65(3):545–569, 2002).
Similar content being viewed by others
References
Scott Aaronson, Bariş Aydinlioǧlu, Harry Buhrman, John Hitchcock & Dieter van Melkebeek (2010). A Note on Exponential Circuit Lower Bounds from Derandomizing Arthur-Merlin Games. Technical Report TR10-174, Electronic Colloquium on Computational Complexity.
Benny Applebaum (2014). Cryptography in Constant Parallel Time. Information Security and Cryptography. Springer, 1–185.
Vikraman Arvind, Johannes Köbler (2001) On Pseudorandomness and Resource-Bounded Measure. Theoretical Computer Science 255(1-2): 205–221
Bariş Aydinlioǧlu, Dan Gutfreund, John Hitchcock, Akinori Kawachi (2011) Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. Computational Complexity 20(2): 329–366
Nayantara Bhatnagar, Andrej Bogdanov & Elchanan Mossel (2011). The Computational Complexity of Estimating MCMC Convergence Time. In Proceedings of the 15th International Workshop on Randomization and Computation, 424–435.
Andrej Bogdanov, Elchanan Mossel & Salil Vadhan (2008). The Complexity of Distinguishing Markov Random Fields. In Proceedings of the 12th International Workshop on Randomization and Computation, 331–342.
Elmar Böhler, Christian Glasser, Daniel Meister (2006) Error-Bounded Probabilistic Computations Between MA and AM. Journal of Computer and System Sciences 72(6): 1043–1076
Anindya De & Thomas Watson (2012). Extractors and Lower Bounds for Locally Samplable Sources. ACM Transactions on Computation Theory 4(1).
Zeev Dvir, Dan Gutfreund, Guy Rothblum & Salil Vadhan (2011). On Approximating the Entropy of Polynomial Mappings. In Proceedings of the 2nd Innovations in Computer Science Conference, 460–475.
Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum (2003) The Relative Complexity of Approximate Counting Problems. Algorithmica 38(3): 471–500
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy (1996) Interactive Proofs and the Hardness of Approximating Cliques. Journal of the ACM 43(2): 268–292
Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans (2008) On the Complexity of Succinct Zero-Sum Games. Computational Complexity 17(3): 353–376
Oded Goldreich (2006). On Promise Problems: A Survey. In Essays in Memory of Shimon Even, 254–290. Springer.
Oded Goldreich, Amit Sahai & Salil Vadhan (1999). Can Statistical Zero Knowledge Be Made Non-Interactive? or On the Relationship of SZK and NISZK. In Proceedings of the 19th International Cryptology Conference, 467–484.
Shafi Goldwasser & Michael Sipser (1986). Private Coins versus Public Coins in Interactive Proof Systems. In Proceedings of the 18th ACM Symposium on Theory of Computing, 59–68.
Johan Håstad (1999) Clique is Hard to Approximate Within n 1-ε. Acta Mathematica 182: 105–142
Mark Jerrum, Leslie Valiant, Vijay Vazirani (1986) Random Generation of Combinatorial Structures from a Uniform Distribution. Theoretical Computer Science 43: 169–188
Valentine Kabanets, Charles Rackoff & Stephen Cook (2000). Efficiently Approximable Real-Valued Functions. Technical Report TR00-034, Electronic Colloquium on Computational Complexity.
Jesse Kamp, Anup Rao, Salil Vadhan, David Zuckerman (2011) Deterministic Extractors for Small-Space Sources. Journal of Computer and System Sciences 77(1): 191–220
Adam Klivans, Dieter van Melkebeek (2002) Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. SIAM Journal on Computing 31(5): 1501–1526
Greg Kuperberg (2009). How Hard Is It to Approximate the Jones Polynomial? url http://arxiv.org/abs/0908.0512.
Rune Lyngsø, Christian Pedersen (2002) The Consensus String Problem and the Complexity of Comparing Hidden Markov Models. Journal of Computer and System Sciences 65(3): 545–569
Peter Bro Miltersen, Vinodchandran N. V. (2005) Derandomizing Arthur-Merlin Games Using Hitting Sets. Computational Complexity 14(3): 256–279
Elchanan Mossel, Christopher Umans (2002) On the Complexity of Approximating the VC Dimension. Journal of Computer and System Sciences 65(4): 660–671
Stuart Russell & Peter Norvig (2010). Artificial Intelligence – A Modern Approach. Pearson Education, third international edition.
Ronen Shaltiel, Christopher Umans (2006) Pseudorandomness for Approximate Counting and Sampling. Computational Complexity 15(4): 298–341
Alistair Sinclair (1993). Algorithms for Random Generation and Counting: A Markov Chain Approach. Progress in Theoretical Computer Science. Birkhäuser.
Larry Stockmeyer (1985) On Approximation Algorithms for #P. SIAM Journal on Computing 14(4): 849–861
Luca Trevisan & Salil Vadhan (2000). Extracting Randomness from Samplable Distributions. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, 32–42.
Luca Trevisan, Salil Vadhan, David Zuckerman (2005) Compression of Samplable Sources. Computational Complexity 14(3): 186–227
Salil Vadhan (2013). A Study of Statistical Zero-Knowledge Proofs. Springer.
Leslie Valiant (1979a) The Complexity of Computing the Permanent. Theoretical Computer Science 8: 189–201
Leslie Valiant (1979b) The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing 8(3): 410–421
Nikolai Vereshchagin (1992). On the Power of PP. In Proceedings of the 7th Structure in Complexity Theory Conference, 138–143.
Emanuele Viola (2011). Extractors for Circuit Sources. In Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science, 220–229.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Watson, T. The complexity of estimating min-entropy. comput. complex. 25, 153–175 (2016). https://doi.org/10.1007/s00037-014-0091-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-014-0091-2