Posted by: atri | September 18, 2007

Project 6: Linear Programming bounds on codes

As we have seen in class, for the worst case noise model, the trade-off that we are interested in that between the rate and the (relative) distance of the code. The optimal trade-off is known when the alphabet size is large enough (for example, when the alphabet size is at least the block length of the code). However, the optimal trade-off for smaller alphabets (and binary codes in particular) is still not known. For a given relative distance the best known lower bound (called the Gilbert-Varshamov bound, which we will see in class) on rate is achieved by random codes while the best known upper bound on rate uses linear programming. The latter is focus of this project.

A recent paper on this topic is On Delsarte’s Linear Programming Bounds for Binary Codes (FOCS05) by Navon and Samorodnitsky. Some background material related to this topic can be found in these lecture notes from Madhu Sudan‘s coding theory course.


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s


%d bloggers like this: