Optimal rate code constructions for computationally simple channels

DOI10.1145/2936015zbMATH Open1407.94009OpenAlexW2963279554MaRDI QIDQ3177812FDOQ3177812

Authors

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.4017

zbMATH Keywords

pseudorandomnesserror-correcting codescomputationally bounded channels

Mathematics Subject Classification ID

Communication theory (94A05) Channel models (including quantum) in information and communication theory (94A40) Decoding (94B35)

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 $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 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. (1) 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 channels add an arbitrary error vector $ein{0,1}^N$ of weight at most $pN$ to the transmitted word; the vector $e$ can depend on the code but not on the particular transmitted word. (2) List-decoding for polynomial-time channels: For every constant $c>0$, we give a Monte Carlo construction of an code with optimal rate (arbitrarily close to $1-H(p)$) that efficiently recovers a short list containing the correct message with high probability for channels describable by circuits of size at most $N^c$. We justify the relaxation to list-decoding by showing that even with bounded channels, uniquely decodable codes cannot have positive rate for $p>1/4$.

Recommendations

• Theory of Cryptography
• Explicit list-decodable codes with optimal rate for computationally bounded channels
• Explicit List-decodable codes with optimal rate for computationally bounded channels
• Transparent error correcting in a computationally bounded world
• Error-correcting codes against chosen-codeword attacks

Cited in

(21)

• Rate-Constrained Simulation and Source Coding i.i.d. Sources
• Minimum Rate Coding for LTI Systems Over Noiseless Channels
• Causal erasure channels
• An operational characterization of mutual information in algorithmic information theory
• Explicit List-decodable codes with optimal rate for computationally bounded channels
• Limited view adversary codes: bounds, constructions and applications
• Transparent error correcting in a computationally bounded world
• Disjoint difference families and their applications
• Explicit list-decodable codes with optimal rate for computationally bounded channels
• Focused codes for channels with skewed errors
• Deterministic rateless codes for BSC
• Error-correcting codes against chosen-codeword attacks
• A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy
• Non-malleable codes with optimal rate for poly-size circuits
• scientific article; zbMATH DE number 7559096 (Why is no real title available?)
• Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
• Oblivious Communication Channels and Their Capacity
• What can cryptography do for coding theory? (Abstract)
• Efficient error-correcting codes for sliding windows
• Theory of Cryptography
• Explicit rateless codes for memoryless binary-input output-symmetric channels

This page was built for publication: Optimal rate code constructions for computationally simple channels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177812)