### Optimal Rate Code Constructions for Computationally Simple ChannelsOptimal Rate Code Constructions for Computationally Simple Channels Access Restriction
Subscribed

 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

Source: ACM Digital Library