New answers tagged

1

The function wouldn't be one-to-one otherwise. The size of the set in the left is $|A|$, and its image would be of size at most $2^l<2^{H_0}=|A|$, therefore, the function wouldn't be injective and thus you wont be able to de-compress some of the data. Therefore it will be a lossy-compression for any $l<H_0$.


2

One possible direction is looking at the (computational) hardness of distributions. For example, a family of distributions $\{\mathcal{P}_n\}_{n\in\mathbb{N}}$ where $\mathcal{P}_n$ is a distribution over $\{0,1\}^n$ is called polynomialy-samplable (you can substitute here any other type of time/space restriction) if there exists a probabilistic polynomial ...


2

Suppose that we have a random source $X$, and we wish to encode many independent samples $x_1,\ldots,x_n$ taken from $X$. An compression scheme is an algorithm that converts $n$ samples of $X$ to a binary string in a reversible way. Shannon showed that the optimal compression scheme produces binary strings of length roughly $nH(X)$, where $H(X)$ is the ...


Top 50 recent answers are included