Compression theory reference?

Matt Crawford crawdad at
Tue Aug 31 18:07:30 EDT 2004

On Aug 31, 2004, at 15:56, John Denker wrote:

>  4) Don't forget the _recursion_ argument.  Take their favorite
> algorithm (call it XX).  If their claims are correct, XX should
> be able to compress _anything_.   That is, the output of XX
> should _always_ be at least one bit shorter than the input.
> Then the compound operation XX(XX(...)) should produce something
> two bits shorter than the original input.  If you start with a
> N-bit message and apply the XX function N-1 times, you should be
> able to compress each and every message down to a single bit.

Plus a string of log(N) bits telling you how many times to apply the 
decompression function!
Uh-oh, now goes over the judge's head ...

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list