Codes for computationally simple channels: Explicit constructions with optimal rate

In this paper, we consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently “simple ” circuit. Codes for such channel models are attractive since, like codes for standard adversarial errors, they can handle channels whose true behavior is unknown or varying over time. For three classes of channels, we provide explicit, efficiently encodable/decodable codes of optimal rate where only inefficiently decodable codes were previously known. In each case, we provide one encoder/decoder that works for every channel in the class. The encoders are randomized, and probabilities are taken over the (local, unknown to the decoder) coins of the encoder and those of the channel. Unique decoding for additive errors. We give the first construction of a poly-time encod-able/decodable code for additive (a.k.a. oblivious) channels that achieve the Shannon capacity 1−H(p). These are channels which add an arbitrary error vector e ∈ {0, 1}N of weight at mos