Access Restriction

Author Guruswami, Venkatesan ♦ Smith, Adam
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Computationally bounded channels ♦ Error-correcting codes ♦ Pseudorandomness
Abstract 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 $\textit{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 $\textit{unknown}$ or $\textit{varying}$ over time. For two classes of channels, we provide explicit, efficiently encodable/decodable codes of optimal rate where only $\textit{in}efficiently$ decodable codes were previously known. In each case, we provide one encoder/decoder that works for $\textit{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 $\textit{additive}$ (a.k.a. $\textit{oblivious})$ channels that achieve the Shannon capacity 1 ™ $\textit{H}(\textit{p}).$ These are channels that add an arbitrary error vector $\textit{e}$ ∈ {0, $1}^{N}$ of weight at most $\textit{pN}$ to the transmitted word; the vector $\textit{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 $\textit{c}$ > 0, we construct codes with optimal rate (arbitrarily close to 1 ™ $\textit{H}(\textit{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 $(\textit{p}$ > 1/4), codes that are uniquely decodable for a modest class of channels (online, memoryless, nonuniform channels) cannot have positive rate.
Description Author Affiliation: Carnegie Mellon University, PA, USA (Guruswami, Venkatesan); Pennsylvania State University, PA, USA (Smith, Adam)
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 4
Page Count 37
Starting Page 1
Ending Page 37

Open content in new tab

   Open content in new tab
Source: ACM Digital Library