CaltechAUTHORS
  A Caltech Library Service

The hardness of decoding linear codes with preprocessing

Bruck, Jehoshua and Naor, Moni (1990) The hardness of decoding linear codes with preprocessing. IEEE Transactions on Information Theory, 36 (2). pp. 381-385. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetit90b

[img]
Preview
PDF
See Usage Policy.

442Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetit90b

Abstract

The problem of maximum-likelihood decoding of linear block codes is known to be hard. The fact that the problem remains hard even if the code is known in advance, and can be preprocessed for as long as desired in order to device a decoding algorithm, is shown. The hardness is based on the fact that existence of a polynomial-time algorithm implies that the polynomial hierarchy collapses. Thus, some linear block codes probably do not have an efficient decoder. The proof is based on results in complexity theory that relate uniform and nonuniform complexity classes.


Item Type:Article
Additional Information:© Copyright 1990 IEEE. Reprinted with permission. Manuscript received October 10, 1988; revised July 12, 1989. The material in this paper was partially presented at the 1990 IEEE Information Theory Symposium, San Diego, CA, January 14-19. The authors thank Dr. Mario Blaum for useful discussions and the Associate Editor, Dr. Don Coppersmith, for his comments.
Subject Keywords:decoding; error correction codes; complexity theory
Record Number:CaltechAUTHORS:BRUieeetit90b
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetit90b
Alternative URL:http://dx.doi.org/10.1109/18.52484
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5703
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:29 Oct 2006
Last Modified:26 Dec 2012 09:14

Repository Staff Only: item control page