Few of the projects will require some knowledge of linear programming and list decoding. The purpose of this entry is to give a (very brief) introduction to these topics. Note that we will cover list decoding is some details in the latter part of the course.

__Linear programming__ is a way to represent optimization problems with linear objective functions that are subject to linear constraints (here linear means that the constraints and the objective functions are linear combinations (over the reals) of the input variables). Linear programming and its generalization __convex optimization__ have been used heavily in algorithms (in both __theoretical computer science__ and in practice). Projects __6__ and __9__ will involve studying two different applications of linear programming in coding theory. For a more comprehensive coverage, see the books titled __Convex Optimization__ by Boyd and Vendenberghe (available for free online) and __Combinatorial Optimization- Polyhedra and Efficiency__ by Schrijver.

List decoding is a generalization of the (unique) decoding problem that we have seen in class. Formally, the list decoding problem for a code of block length is the following:

- Given a bound on the fraction of errors , a list decoder has to return, given any received word , all codewords such that .

See this __chapter__ of my thesis for a quickish introduction to list decoding (and some known combinatorial results on list decoding). Projects __5__ and __13__ will require list decoding as will parts of projects __2__ and __10__.

## Leave a Reply