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 that 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 two 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 polynomial-time encodable/decodable code for additive (a.k.a. oblivious) channels that achieve the Shannon capacity 1 − H( p). These are channels that add an arbitrary error vector e ∈ {0, 1} N of weight at most pN to the transmitted word; the vector e can depend on the code but not on the randomness of the encoder or the particular transmitted word. Such channels capture binary symmetric errors and burst errors as special cases. List decoding for polynomial-time channels: For every constant c > 0, we construct codes with optimal rate (arbitrarily close to 1 − H( p)) that efficiently recover a short list containing the correct message with high probability for channels describable by circuits of size at most N c . Our construction is not fully explicit but rather Monte Carlo (we give an algorithm that, with high probability, produces an encoder/decoder pair that works for all time N c channels). We are not aware of any channel models considered in the information theory literature other than purely adversarial channels, which require more than linear-size circuits to implement. We justify the relaxation to list decoding with an impossibility result showing that, in a large range of parameters ( p > 1/4), codes that are uniquely decodable for a modest class of channels (online, memoryless, nonuniform channels) cannot have positive rate. V. Guruswami and A. Smith efficient (i.e., polynomial-time encodable and decodable) binary codes for list decoding with near-optimal rate is a major open problem. 1 Therefore, our goal is to exploit the computational restrictions on the channel to get efficiently list-decodable codes. Computationally bounded channels. We consider channels whose behavior on Nbit inputs is described by a circuit of size T(N) (for example, T(N) = O(N 2 )). We sometimes call this the time-bounded model and refer to T(·) as a time bound. We do not know of any channel models considered in the information theory literature other than purely adversarial channels, which require more than linear time to implement. We also discuss (online) space-bounded channels; these channels make a single pass over the transmitted codeword, deciding which locations to corrupt as they go, and are limited to storing at most S(N) bits (that is, they can be describe by one-pass branching programs of width at most 2 S(N) ). Logarithmic space channels, in particular, can be realized by polynomial-size circuits. List decoding for polynomial-time channels. Our main contribution for timebounded channels is a construction of polynomial-time encodable and list-decodable codes that approach the optimal rate for channels whose time bound is a polynomial in the block length N. Specifically, we give an efficiently computable encoding function, Enc, that stochastically encodes the message m into Enc(m; r), where r is private randomness chosen at the encoder, such that for every message m and time N c -bounded channel W, the decoder takes W(Enc(m; r)) as input and returns a small list of messages that, with high probability over r and the coins of the channel, contains the real message m. The size of the list is polynomial in 1/ε, where N(1 − H( p) − ε) is the length of the transmitted messages. We stress that the decoder does not know the choice of random bits r made at the encoder. The construction of our encoding function Enc(·, ·) is Monte Carlo-we give a randomized algorithm that, with high probability, produces an encoder/decoder pair Enc/Dec reliably communicate across all time-N c -bounded channels (Definition 3.3). The randomized construction is polynomial time, and the resulting function Enc(m; r) can be computed from m, r in deterministic polynomial time. However, we do not know how to efficiently check and certify that a particular encoder Enc has the claimed properties. Obtaining fully explicit constructions remains an intriguing open problem. In the case of polynomial-time bounded channels, it seems unlikely that one can solve the problem without additional complexity assumptions (such as the existence of certain pseudorandom generators). In the case of online logspace-bounded channel, it may be possible to obtain fully explicit constructions without complexity assumptions (using, for example, Nisan's pseudorandom generators for logspace). We will elaborate on this aspect in Section 9. One technicality is that the decoder need not return all words within a distance pN of the received word (as is the case for the standard "combinatorial" notion of list decoding), but it must return the correct message as one of the candidates with high probability. This notion of list decoding is natural for stochastic codes in communication applications. In fact, it is exactly the notion that is needed in constructions that "sieve" the list, such as in Guruswami [2003] and Micali et al. [2005], and one application of our results is a uniquely decodable code for the public-key model (assuming a specific polynomial-time bound), strengthening results of Micali et al. [2005]. See the discussion of related work in Section 2 for a more precise statement. For both the additive and time-bounded models, our constructions require new methods for applying tools from cryptography and derandomization to coding-theoretic problems. We give a brief high-level discussion of these techniques next. An expanded overview the approach behind our code construction appears in Section 6. 1 Over large alphabets, explicit optimal rate list-decodable codes are known. Control/payload construction. In our constructions, we develop several new techniques. The first is a novel "reduction" from the standard coding setting with no setup to the setting of shared secret randomness. In models in which errors are distributed evenly, such a reduction is relatively simple [Ahlswede 1978]; however, this reduction fails against adversarial errors. Instead, we show how to hide the secret randomness (the control information) inside the main codeword (the payload) in such a way that the decoder can learn the control information but (a) the control information remains hidden to a bounded channel and (b) its encoding is robust to a certain, weaker class of errors. We feel this technique should be useful in other settings of bounded adversarial behavior. Our reduction can also be viewed as a novel way of bootstrapping from "small" codes, which can be decoded by brute force, to "large" codes, which can be decoded efficiently. The standard way to do this is via concatenation; unfortunately, concatenation does not work well even against mildly unpredictable models, such as the additive error model. Second, our results further develop a surprising connection between coding and pseudorandomness. Hiding the "control information" from the channel requires us to make different settings of the control information indistinguishable from the channel's point of view. Thus, our proofs apply techniques from cryptography together with constructions of pseudorandom objects (generators, permutations, and samplers) from derandomization. Typically, the "tests" that must be fooled are compositions of the channel (which we assume has low complexity) with some subroutine of the decoder (which we design to have low complexity). The connection to pseudorandomness appeared in a simpler form in the previous work on bounded channels [Lipton 1994; Galil et al. 1995; Micali et al. 2005] ; our use of this connection is significantly more delicate. The necessary pseudorandom permutations and samplers can be explicitly constructed, and the construction of the needed complexity-theoretic pseudorandom generators is where we uses randomness in our construction. For the case of additive errors, information-theoretic objects that we can construct deterministically efficiently (such as t-wise-independent strings) suffice and we get a fully explicit construction. There are several lines of work aimed at handling adversarial, or partly adversarial, errors with rates near the Shannon capacity. We survey them briefly here and highlight the relationship to our results. List decoding. List decoding was introduced in the late 1950s [Elias 1957; Wozencraft 1958] and has witnessed a lot of recent algorithmic work (cf. the survey [Guruswami 2007] ). Under list decoding, the decoder outputs a small list of messages that must include the correct message. Random coding arguments demonstrate that there exist binary codes of rate 1 − H( p) − ε that can tolerate pN adversarial errors if the decoder is allowed to output a list of size O(1/ε) [Elias 1991; Zyablov and Pinsker 1982; Guruswami et al. 2002] . The explicit construction of binary list-decodable codes with rate close to 1 − H( p), however, remains a major open question. We provide such codes for the special case of corruptions introduced by space-or time-bounded channels. Adding Setup-Shared Randomness. Another relaxation is to allow randomized coding strategies where the sender and receiver share "secret" randomness, hidden from the channel, which is used to pick a particular, deterministic code at random from a family of codes. Such randomized strategies were called private codes in Langberg [2004]. Using this secret shared randomness, one can transmit at rates approaching
Explicit codes of rate approaching 1 − h(p) to correct pn oblivious bit flips (in the sense of Theorem 1.1, with randomized encoding) were given in REF .
Optimal Rate Code Constructions for Computationally Simple Channels
JACM
Computer Science Mathematics