Title :
The complexity of approximating the entropy
Author :
Batu, Tugkan ; Dasgupta, Sanjoy ; Kumar, Ravi ; Rubinfeld, Ronitt
Author_Institution :
Dept. of Comput. & Inf. Sci., Pennsylvania Univ., Philadelphia, PA, USA
fDate :
6/24/1905 12:00:00 AM
Abstract :
The Shannon entropy is a measure of the randomness of a distribution, and plays a central role in statistics, information theory, and data compression. Knowing the entropy of a random source can shed light on the compressibility of data produced by such a source. We consider the complexity of approximating the entropy under various different assumptions on the way the input is presented
Keywords :
computational complexity; data compression; entropy; Shannon entropy; complexity; data compressibility; data compression; distribution randomness; entropy approximation; information theory; random source; statistics; Algorithm design and analysis; Approximation algorithms; Computational efficiency; Entropy; Information theory; Physics; Probability; Statistical analysis; Statistical distributions; Upper bound;
Conference_Titel :
Computational Complexity, 2002. Proceedings. 17th IEEE Annual Conference on
Conference_Location :
Montreal, Que.
Print_ISBN :
0-7695-1468-5
DOI :
10.1109/CCC.2002.1004329
