On optimal placements of processors in Tori networks
M. Blaum, J. Bruck, et al.
IPDPS 1996
Summary form only given. The problem of maximum-likelihood decoding of linear block codes is known to be hard. It has been shown by the authors 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 devise a decoding algorithm. The hardness is based on the fact that existence of a polynomial-time algorithm implies that the polynomial hierarchy collapses. This means that 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.
M. Blaum, J. Bruck, et al.
IPDPS 1996
M. Blaum, J. Bruck
ISIT 1993
N. Alon, Moni Naor
IEEE Transactions on Industry Applications
J. Bruck, Luc de Coster, et al.
IPDPS 1994