The complexity of estimating min-entropy. (English) Zbl 1336.68109
Summary: O. Goldreich et al. [Lect. Notes Comput. Sci. 1666, 467–484 (1999; Zbl 0942.68046)] 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 R. B. Lyngsø and C. N. S. Pedersen on hidden Markov models [J. Comput. Syst. Sci. 65, No. 3, 545–569 (2002; Zbl 1059.68048)].
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 94A17 | Measures of information, entropy |
References:
| [1] | 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. · Zbl 0415.68008 |
| [2] | Benny Applebaum (2014). Cryptography in Constant Parallel Time. Information Security and Cryptography. Springer, 1-185. · Zbl 1298.94001 |
| [3] | Vikraman Arvind, Johannes Köbler (2001) On Pseudorandomness and Resource-Bounded Measure. Theoretical Computer Science 255(1-2): 205-221 · Zbl 0974.68063 · doi:10.1016/S0304-3975(99)00164-4 |
| [4] | 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 · Zbl 1230.68076 · doi:10.1007/s00037-011-0010-8 |
| [5] | 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. · Zbl 1343.68289 |
| [6] | 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. · Zbl 1159.68042 |
| [7] | 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 · Zbl 1100.68023 · doi:10.1016/j.jcss.2006.05.001 |
| [8] | Anindya De & Thomas Watson (2012). Extractors and Lower Bounds for Locally Samplable Sources. ACM Transactions on Computation Theory 4(1). · Zbl 1322.65009 |
| [9] | 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. · Zbl 0597.68056 |
| [10] | Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum (2003) The Relative Complexity of Approximate Counting Problems. Algorithmica 38(3): 471-500 · Zbl 1138.68424 |
| [11] | 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 · Zbl 0882.68129 · doi:10.1145/226643.226652 |
| [12] | Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans (2008) On the Complexity of Succinct Zero-Sum Games. Computational Complexity 17(3): 353-376 · Zbl 1162.91302 · doi:10.1007/s00037-008-0252-2 |
| [13] | Oded Goldreich (2006). On Promise Problems: A Survey. In Essays in Memory of Shimon Even, 254-290. Springer. · Zbl 1162.91302 |
| [14] | 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. · Zbl 0942.68046 |
| [15] | 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. |
| [16] | Johan Håstad (1999) Clique is Hard to Approximate Within n1-ε. Acta Mathematica 182: 105-142 · Zbl 0989.68060 · doi:10.1007/BF02392825 |
| [17] | Mark Jerrum, Leslie Valiant, Vijay Vazirani (1986) Random Generation of Combinatorial Structures from a Uniform Distribution. Theoretical Computer Science 43: 169-188 · Zbl 0597.68056 · doi:10.1016/0304-3975(86)90174-X |
| [18] | Valentine Kabanets, Charles Rackoff & Stephen Cook (2000). Efficiently Approximable Real-Valued Functions. Technical Report TR00-034, Electronic Colloquium on Computational Complexity. · Zbl 0974.68063 |
| [19] | 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 · Zbl 1232.68094 · doi:10.1016/j.jcss.2010.06.014 |
| [20] | 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 · Zbl 1016.68060 · doi:10.1137/S0097539700389652 |
| [21] | Greg Kuperberg (2009). How Hard Is It to Approximate the Jones Polynomial? url http://arxiv.org/abs/0908.0512. · Zbl 1337.68109 |
| [22] | 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 · Zbl 1059.68048 · doi:10.1016/S0022-0000(02)00009-0 |
| [23] | Peter Bro Miltersen, Vinodchandran N. V. (2005) Derandomizing Arthur-Merlin Games Using Hitting Sets. Computational Complexity 14(3): 256-279 · Zbl 1085.68058 · doi:10.1007/s00037-005-0197-7 |
| [24] | Elchanan Mossel, Christopher Umans (2002) On the Complexity of Approximating the VC Dimension. Journal of Computer and System Sciences 65(4): 660-671 · Zbl 1059.68049 · doi:10.1016/S0022-0000(02)00022-3 |
| [25] | Stuart Russell & Peter Norvig (2010). Artificial Intelligence - A Modern Approach. Pearson Education, third international edition. · Zbl 0835.68093 |
| [26] | Ronen Shaltiel, Christopher Umans (2006) Pseudorandomness for Approximate Counting and Sampling. Computational Complexity 15(4): 298-341 · Zbl 1125.68058 · doi:10.1007/s00037-007-0218-9 |
| [27] | Alistair Sinclair (1993). Algorithms for Random Generation and Counting: A Markov Chain Approach. Progress in Theoretical Computer Science. Birkhäuser. · Zbl 0780.68096 |
| [28] | Larry Stockmeyer (1985) On Approximation Algorithms for #P. SIAM Journal on Computing 14(4): 849-861 · Zbl 0589.68031 · doi:10.1137/0214060 |
| [29] | Luca Trevisan & Salil Vadhan (2000). Extracting Randomness from Samplable Distributions. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, 32-42. · Zbl 1085.68041 |
| [30] | Luca Trevisan, Salil Vadhan, David Zuckerman (2005) Compression of Samplable Sources. Computational Complexity 14(3): 186-227 · Zbl 1085.68041 · doi:10.1007/s00037-005-0198-6 |
| [31] | Salil Vadhan (2013). A Study of Statistical Zero-Knowledge Proofs. Springer. · Zbl 06236023 |
| [32] | Leslie Valiant (1979a) The Complexity of Computing the Permanent. Theoretical Computer Science 8: 189-201 · Zbl 0415.68008 · doi:10.1016/0304-3975(79)90044-6 |
| [33] | Leslie Valiant (1979b) The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing 8(3): 410-421 · Zbl 0419.68082 · doi:10.1137/0208032 |
| [34] | Nikolai Vereshchagin (1992). On the Power of PP. In Proceedings of the 7th Structure in Complexity Theory Conference, 138-143. |
| [35] | Emanuele Viola (2011). Extractors for Circuit Sources. In Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science, 220-229. · Zbl 1292.68117 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
