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)
Measures of information, entropy (94A17) Approximation algorithms (68W25) Sampling theory in information and communication theory (94A20) Nonparametric inference (62G99)
Related Items (14)
Sampling Correctors ⋮ Sublinear algorithms for approximating string compressibility ⋮ Coincidences and estimation of entropies of random variables with large cardinalities ⋮ Bounds from a card trick ⋮ Testing shape restrictions of discrete distributions ⋮ An Automatic Inequality Prover and Instance Optimal Identity Testing ⋮ On the power of conditional samples in distribution testing ⋮ Is submodularity testable? ⋮ Proofs of Proximity for Distribution Testing ⋮ Quantum spectrum testing ⋮ A simple method for estimating the entropy of neural activity ⋮ Invariance in Property Testing ⋮ A sublinear-time approximation scheme for bin packing ⋮ Testing Probability Distributions using Conditional Samples
This page was built for publication: The Complexity of Approximating the Entropy