Posted by: atri | September 18, 2007

## Primers: Linear Programming and List Decoding

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 $C$ of block length $n$ is the following:

• Given a bound on the fraction of errors $\rho$, a list decoder has to return, given any received word $\mathbf{y}$, all codewords $c\in C$ such that $\Delta(c,\mathbf{y})\le\rho n$.

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.