Private codes
or
Succinct random codes that are (almost) perfect
Coding theory addresses the design and analysis of codes that enable communication over noisy channels. Two types of channels that have been extensively considered are the "binary symmetric" channel and the "adversarial" channel. In a binary symmetric channel each bit of the sent message is flipped independently with some probability p, implying that the noise imposed by the channel is "random" in nature where the "amount" of noise is determined by p. In an adversarial channel the message is treated as a whole, and the noise may be an arbitrary (and malicious) function of the message being sent, as long as it does not effect more that a certain fraction (say p) of the bits transmitted.
Roughly speaking, any code designed for an adversarial channel can be used on a corresponding binary symmetric channel successfully, whereas the contrary is not necessarily true. In this work we will present a construction which transforms the "best" codes for binary symmetric channels into codes for corresponding adversarial channels.
Of course there is a catch: the "codes" we present assume that the sender and the receiver of the message have a joint secret random string (which is not known to the channel). These codes are referred to as "private" codes (also known as "random codes", i.e. a distribution over codes as apposed to a single code). Intuitively, this private randomness allows a reduction between the random and adversarial channels. Such a reduction is simple once the size of the joint random string is larger than n\log{n} (here the codes are a subset of {0,1}^n).
In this work we present private codes in which this size is O(log{n}). Moreover, we show that our result is tight. Namely, to design private codes that allow communication over adversarial channels which meet the bounds achievable when communicating over binary symmetric channels, an amount of \Omega(\log{n}) shared random bits are required. To the best of our knowledge, no prior results of this nature have been presented in the past. As part of our proof we establish a connection between list decodable codes and private codes which complements a recent result of Guruswami (CCC '03) on list decoding with side information.