Optimal Error Correction for Computationally Bounded Noise
- Resource Type
- Periodical
- Authors
- Micali, S.; Peikert, C.; Sudan, M.; Wilson, D. A.
- Source
- IEEE Transactions on Information Theory IEEE Trans. Inform. Theory Information Theory, IEEE Transactions on. 56(11):5673-5680 Nov, 2010
- Subject
- Communication, Networking and Broadcast Technologies
Signal Processing and Analysis
Encoding
Receivers
Error analysis
Decoding
Probabilistic logic
Public key
Noise
Adversarial error
channel modelling
computationally bounded channels
- Language
- ISSN
- 0018-9448
1557-9654
For adversarial but computationally bounded models of error, we construct appealingly simple and efficient cryptographic encoding and unique decoding schemes whose error-correction capability is much greater than classically possible. In particular: For binary alphabets, we construct positive-rate coding schemes that are uniquely decodable under a $1/2 - \gamma$ error rate for any constant $\gamma > 0$.