What are some interesting differences between the set of lossless and lossy compressible binary sequences (lossy := there exists a decompression algorithm that can recover over 50% of the sequence’s bits)?

How can we characterize the set of sequences that under the lossy def become compressible that under the lossless def were not?

  • $\begingroup$ You have to be a bit more precise about the condition "can recover over 50% of the sequence’s bits". Presumably you mean in the limit -- perhaps limsup of the average error is bounded away from $1/2$. $\endgroup$ – Aryeh Sep 11 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.