Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Distribution Support Size Estimation:
TR05-125 | 2nd November 2005
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

We raise the question of approximating compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present algorithms and lower bounds for approximating compressibility with respect to ... more >>>

TR16-186 | 19th November 2016
Jayadev Acharya, Hirakendu Das, Alon Orlitsky, Ananda Theertha Suresh

A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation

The advent of data science has spurred interest in estimating properties of discrete distributions over large alphabets. Fundamental symmetric properties such as support size, support coverage, entropy, and proximity to uniformity, received most attention, with each property estimated using a different technique and often intricate analysis tools.

Motivated by the ... more >>>

ISSN 1433-8092 | Imprint