Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Is the following scenario theoretically possible, or provably impossible?
Alice generates a 1 GiB file with random bits and sends it to Bob. This file is a shared dictionary they call Q. Now, Alice and Bob starts sending each other new files with arbitrary entropy, each of them < 1 MiB, but they compress them with a clever algorithm that exploits information in Q, typically breaking the Shannon limit.
This is provably impossible. The proof of Shannon's theorem goes through as usual.
As a simple example, suppose that are looking for an algorithm that compresses all $n$-bit strings to smaller strings. This is impossible since there are $2^n$ possible inputs, but only $2^n-1$ possible outputs. The proof of Shannon's theorem is very similar. Note how $Q$ makes absolutely no difference.
What happens if you choose a random 1 MiB window of $Q$ as your file? This can easily be compressed to 30 bits, by sending the location of the window. However, in this case the entropy of $Q$ is indeed at most 30 bits, since there are at most $2^{30}$ different windows.
