Conference paper
Association control in mobile wireless networks
Minkyong Kim, Zhen Liu, et al.
INFOCOM 2008
The problem of maximum likelihood decoding of linear block codes is known to be hard [3]. It is shown 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. Namely, 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. © 1990 IEEE
Minkyong Kim, Zhen Liu, et al.
INFOCOM 2008
Raghu Krishnapuram, Krishna Kummamuru
IFSA 2003
Eric Price, David P. Woodruff
FOCS 2011
Oliver Bodemer
IBM J. Res. Dev