The complexity of estimating min-entropy

• 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

  Article  MathSciNet  Google Scholar 

• 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

  Article  MathSciNet  MATH  Google Scholar 

• 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

  Article  MathSciNet  MATH  Google Scholar 

• 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

  Google Scholar 

• 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

  Article  MathSciNet  MATH  Google Scholar 

• Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans (2008) On the Complexity of Succinct Zero-Sum Games. Computational Complexity 17(3): 353–376

  Article  MathSciNet  MATH  Google Scholar 

• 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

  Article  MathSciNet  MATH  Google Scholar 

• Mark Jerrum, Leslie Valiant, Vijay Vazirani (1986) Random Generation of Combinatorial Structures from a Uniform Distribution. Theoretical Computer Science 43: 169–188

  Article  MathSciNet  MATH  Google Scholar 

• 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

  Article  MathSciNet  MATH  Google Scholar 

• 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

  Article  MathSciNet  MATH  Google Scholar 

• 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

  Article  MathSciNet  MATH  Google Scholar 

• Peter Bro Miltersen, Vinodchandran N. V. (2005) Derandomizing Arthur-Merlin Games Using Hitting Sets. Computational Complexity 14(3): 256–279

  Article  MathSciNet  MATH  Google Scholar 

• Elchanan Mossel, Christopher Umans (2002) On the Complexity of Approximating the VC Dimension. Journal of Computer and System Sciences 65(4): 660–671

  Article  MathSciNet  MATH  Google Scholar 

• 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

  Article  MathSciNet  MATH  Google Scholar 

• 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

  Article  MathSciNet  MATH  Google Scholar 

• 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

  Article  MathSciNet  MATH  Google Scholar 

• 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

  Article  MathSciNet  Google Scholar 

• Leslie Valiant (1979b) The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing 8(3): 410–421

  Article  MathSciNet  MATH  Google Scholar 

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

Download references