Computer Science – Information Theory
Scientific paper
2010-04-22
Preliminary version in IEEE Symposium on the Foundations of Computer Science (FOCS) 2010
Computer Science
Information Theory
46 pages,1 figure. This version addresses an error in version 1 (proof of correctness of codes for log space) and contains add
Scientific paper
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. 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. (1) Unique decoding for additive errors: We give the first construction of poly-time encodable/decodable codes for additive (a.k.a. oblivious) channels that have rate arbitrarily close to the Shannon capacity 1-H(p). Such channels capture binary symmetric errors and burst errors as special cases. (2) List-decoding for log-space channels: A space-S(n) channel reads and modifies the transmitted codeword as a stream, using at most S(n) bits of workspace on transmissions of n bits. Even for constant S, this captures many models from the literature, including discrete channels with finite memory and arbitrarily varying channels. We give an efficient code with optimal rate (arbitrarily close to 1-H(p)) that recovers a short list containing the correct message with high probability for channels limited to logarithmic space. (3) List-decoding for poly-time channels: For any constant c, assuming the existence of pseudorandom generators, we give a similar list-decoding result for channels describable by circuits of size at most n^c.
Guruswami Venkatesan
Smith Adam
No associations
LandOfFree
Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-693613