Optimal rate code constructions for computationally simple channels

DOI10.1145/2936015zbMATH Open1407.94009arXiv1004.4017OpenAlexW2963279554MaRDI QIDQ3177812FDOQ3177812

Authors:

Publication date: 2 August 2018

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

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$.

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

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

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)

Cited In (21)

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