The Complexity of Approximating the Entropy

DOI10.1137/S0097539702403645MaRDI QIDQ5700573zbMATH OpenFDO

Authors Tuğkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld

Publication date 28 October 2005

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539702403645

zbMATH Keywords

entropy estimationproperties of distributionsproperty testingsublinear algorithms

Mathematics Subject Classification ID

Nonparametric inference (62G99) Approximation algorithms (68W25) Measures of information, entropy (94A17) Sampling theory in information and communication theory (94A20)

Recommendations

• The complexity of estimating Rényi entropy
• The complexity of estimating min-entropy
• Approximate entropy as a measure of system complexity.
• Entropy measures vs. Kolmogorov complexity
• On the estimation of entropy
• scientific article; zbMATH DE number 6159972
• Approximating the hard square entropy constant with probabilistic methods
• scientific article; zbMATH DE number 1114415
• scientific article; zbMATH DE number 1894367

Cited in

(31)

• A sublinear-time approximation scheme for bin packing
• A proof of the Beyer-Stein-Ulam relation between complexity and entropy
• An entropy based measure for comparing distributions of complexity
• Testing shape restrictions of discrete distributions
• Sublinear algorithms for approximating string compressibility
• The complexity of estimating min-entropy
• Sublinear estimation of entropy and information distances
• A near-optimal algorithm for estimating the entropy of a stream
• A near-optimal algorithm for computing the entropy of a stream
• Approximating entropy from sublinear samples
• Optimal bounds for estimating entropy with PMF queries
• An automatic inequality prover and instance optimal identity testing
• On the complexity of computing maximum entropy for Markovian models
• On the Complexity of Breaking Pseudoentropy
• On the complexity of computational problems regarding distributions
• The Leakage-Resilience Limit of a Computational Problem Is Equal to Its Unpredictability Entropy
• A simple method for estimating the entropy of neural activity
• Strong lower bounds for approximating distribution support size and the distinct elements problem
• scientific article; zbMATH DE number 3900670 (Why is no real title available?)
• Coincidences and estimation of entropies of random variables with large cardinalities
• Bounds from a card trick
• Entropy of theK-Satisfiability Problem
• Sampling correctors
• Is submodularity testable?
• Invariance in property testing
• Proofs of proximity for distribution testing
• Testing probability distributions using conditional samples
• Entropy, optimization and counting
• Lifting uniform learners via distributional decomposition
• On the complexity of estimating the effective support size
• A scalable entropy estimator

This page was built for publication: The Complexity of Approximating the Entropy

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