Error Correcting Codes for Uncompressed Messages

by Ofer Grossman and Justin Holmgren.

Oded's comments

Folklore (see below) suggests that list decoding may be yield unique decoding when the original message can be distinguished from the other members of the recovered list by means of its contents. However, as far as I recall, the question of how to guarantee the later condition was not addressed systematically, which is quite typical of all folklore (see below again). This paper address this lacuna by providing a natural model and solving the problem in that model.

On folklore: In contrast to its sociological meaning, in TOC this term typically means some vaguely specified fact that is known to some experts. I wish to highlight two key ingredients regarding this notion: First, that the known fact is not clearly defined (i.e., its definition is lacking when compared to the standard norms of the discipline). Second, that this knowledge is ``shared'' by few people, who typically publicize their claim of knowledge only after others who were excluded from the folklore actually discover it, distill it, study it, and publish it. Needless to say, the practice of excluding some, let alone most, members of the scientific community from the benefit of the ``folklore'' is incompatible with the basic ethos of Science. In particular, one should hope for the elimination of all folklore: Any fact of value should be specified, distilled, worked-out, and published.

The original abstract

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed.

We show that in this setting, it is sub-optimal to use standard error correction. We consider a model where there is a set of “valid messages” which the sender may send that may not be efficiently compressible, but where it is possible for the receiver to recognize valid messages. In this model, we construct a (probabilistic) encoding procedure that achieves better tradeoffs between data rates and error-resilience (compared to just applying a standard error correcting code).

Additionally, our techniques yield improved efficiently decodable (probabilistic) codes for fully compressed messages (the standard setting where the set of valid messages is all binary strings) in the high-rate regime.

See ECCC TR20-038.

Back to list of Oded's choices.