The complexity of estimating min-entropy
From MaRDI portal
Publication:260395
DOI10.1007/s00037-014-0091-2zbMath1336.68109OpenAlexW2028368516MaRDI QIDQ260395
F. Blanchet-Sadri, M. Dambrine
Publication date: 21 March 2016
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-014-0091-2
Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A study of statistical zero-knowledge proofs (to appear)
- The complexity of computing the permanent
- Cryptography in constant parallel time
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- Derandomizing Arthur-Merlin games using hitting sets
- Compression of samplable sources
- On the complexity of succinct zero-sum games
- Random generation of combinatorial structures from a uniform distribution
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- The consensus string problem and the complexity of comparing hidden Markov models.
- On the complexity of approximating the VC dimension.
- The relative complexity of approximate counting problems
- Pseudorandomness for approximate counting and sampling
- Error-bounded probabilistic computations between MA and AM
- The Computational Complexity of Estimating MCMC Convergence Time
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- The Complexity of Distinguishing Markov Random Fields
- On Approximation Algorithms for # P
- The Complexity of Enumeration and Reliability Problems
- Interactive proofs and the hardness of approximating cliques
- Extractors for Circuit Sources
- Extractors and Lower Bounds for Locally Samplable Sources
- Deterministic extractors for small-space sources
- On pseudorandomness and resource-bounded measure
