Optimal rate code constructions for computationally simple channels
From MaRDI portal
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 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 . These channels add an arbitrary error vector of weight at most to the transmitted word; the vector can depend on the code but not on the particular transmitted word. (2) List-decoding for polynomial-time channels: For every constant , we give a Monte Carlo construction of an code with optimal rate (arbitrarily close to ) that efficiently recovers a short list containing the correct message with high probability for channels describable by circuits of size at most . We justify the relaxation to list-decoding by showing that even with bounded channels, uniquely decodable codes cannot have positive rate for .
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
(23)- Explicit list-decodable codes with optimal rate for computationally bounded channels
- Transparent error correcting in a computationally bounded world
- Limited view adversary codes: bounds, constructions and applications
- Error-correcting codes against chosen-codeword attacks
- Deterministic rateless codes for BSC
- Focused codes for channels with skewed errors
- Oblivious Communication Channels and Their Capacity
- Explicit rateless codes for memoryless binary-input output-symmetric channels
- Explicit List-decodable codes with optimal rate for computationally bounded channels
- What can cryptography do for coding theory? (Abstract)
- An operational characterization of mutual information in algorithmic information theory
- Secret sharing with binary shares
- A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy
- Efficient error-correcting codes for sliding windows
- Rate-Constrained Simulation and Source Coding i.i.d. Sources
- Minimum Rate Coding for LTI Systems Over Noiseless Channels
- Causal erasure channels
- Theory of Cryptography
- Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
- Non-malleable codes with optimal rate for poly-size circuits
- Binary codes for error detection and correction in a computationally bounded world
- Error correcting codes for uncompressed messages
- Disjoint difference families and their applications
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)
