The complexity of estimating min-entropy

DOI10.1007/S00037-014-0091-2MaRDI QIDQ260395zbMATH OpenOpenAlexFDO

Authors Thomas Watson

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

zbMATH Keywords

approximate countingcomplexitymin-entropysamplable distributions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Measures of information, entropy (94A17)

Recommendations

• The Complexity of Approximating the Entropy
• Computational analogues of entropy
• On the complexity of computational problems regarding distributions
• The complexity of estimating Rényi entropy
• On the complexity of computing maximum entropy for Markovian models

Cites work

• A study of statistical zero-knowledge proofs (to appear)
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Compression of samplable sources
• Cryptography in constant parallel time
• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• Derandomizing Arthur-Merlin games using hitting sets
• Deterministic extractors for small-space sources
• Error-bounded probabilistic computations between MA and AM
• Extractors and lower bounds for locally samplable sources
• Extractors for Circuit Sources
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• How hard is it to approximate the Jones polynomial?
• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 783783 (Why is no real title available?)
• scientific article; zbMATH DE number 1418312 (Why is no real title available?)
• Interactive proofs and the hardness of approximating cliques
• On Approximation Algorithms for # P
• On pseudorandomness and resource-bounded measure
• On the complexity of approximating the VC dimension.
• On the complexity of succinct zero-sum games
• Pseudorandomness for approximate counting and sampling
• Random generation of combinatorial structures from a uniform distribution
• The complexity of computing the permanent
• The Complexity of Distinguishing Markov Random Fields
• The Complexity of Enumeration and Reliability Problems
• The computational complexity of estimating MCMC convergence time
• The consensus string problem and the complexity of comparing hidden Markov models.
• The relative complexity of approximate counting problems

Cited in

(7)

• Quasi chain rule for min-entropy
• Minimal Entropy Approximations and Optimal Algorithms
• Communication complexity of statistical distance
• The Untold Story of $$\mathsf {SBP}$$
• A minimax approach to one-shot entropy inequalities
• The Complexity of Approximating the Entropy
• From -entropy to KL-entropy: analysis of minimum information complexity density estima\-tion

This page was built for publication: The complexity of estimating min-entropy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q260395)