Posted by: atri | September 12, 2007

Project 14: Complexity issues in coding theory

In class today, we defined the notion of efficient algorithms to be polynomial time algorithms. The most obvious algorithmic questions related to codes are that of encoding and decoding. We have already seen that for linear codes, encoding is always efficient. However, is it true that efficient decoding is always possible? Or is it the case that like most natural optimization problems, this is an NP-hard problem?

In class today, we saw that for the Hamming code, the obvious brute force implementation of the Maximum Likelihood Decoding (MLD) function takes exponential time. However, can one do an efficient implementation of the MLD function? Further, maybe it does not work for the Hamming code but maybe it can done for other codes. Unfortunately, MLD turns out to be a very slippery customer: there are no non-trivial codes known for which efficient implementation of MLD is known. There has been a series of results along this line for about 25 years now. One of the more recent result due to Guruswami and Vardy is their paper titled Maximum-Likelihood Decoding of Reed-Solomon codes is NP-Hard (SODA05).

Another parameter of the code that is not immediately obvious from the definition of a linear code is the distance of the code. The situation here is not as hopeless as MLD– for certain linear codes it is easy to figure our their distance (for most of the linear codes that we will study in the course, this will be the case). However, there do exist linear codes for which it is NP-hard to determine its distance (in fact it is hard even to approximate it). See for example, the paper by Dumer, Micciancio and Sudan titled Hardness of Approximating the Minimum Distance of a Linear Code (FOCS99).



  1. […] is a link to an earlier post that talk about the complexity issues for MLD (and other coding […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s


%d bloggers like this: