The Complexity of Approximating the Entropy
From MaRDI portal
Publication:5700573
DOI10.1137/S0097539702403645zbMath1087.94012MaRDI QIDQ5700573
Tuğkan Batu, Ronitt Rubinfeld, Ravi Kumar, Sanjoy Dasgupta
Publication date: 28 October 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
94A17: Measures of information, entropy
68W25: Approximation algorithms
94A20: Sampling theory in information and communication theory
62G99: Nonparametric inference
Related Items
Sampling Correctors, Invariance in Property Testing, Proofs of Proximity for Distribution Testing, Testing Probability Distributions using Conditional Samples, Coincidences and estimation of entropies of random variables with large cardinalities, Bounds from a card trick, Is submodularity testable?, A sublinear-time approximation scheme for bin packing, Testing shape restrictions of discrete distributions, Quantum spectrum testing, Sublinear algorithms for approximating string compressibility, An Automatic Inequality Prover and Instance Optimal Identity Testing, On the power of conditional samples in distribution testing, A simple method for estimating the entropy of neural activity