Computer Science Colloquium, 2003-2004

New Connections Between Coding Theory and Complexity

Coding theory studies the problem of transmitting data reliably over a noisy channel. Complexity Theory studies the computational complexity of functions. In recent years many new connections between the two seemingly unrelated areas were found. In this talk I shall describe some of these connections.

In particular we shall see the following results:

1. Describe the notion of "Locally Testable Codes" (codes for which we can efficiently verify whether a given word is in the code or far from the code) arising from the PCP theorem.
2. Prove new results for locally testable codes:
   1. Show that there are no good locally testable cyclic codes
   2. Generalization of known constructions of locally testable codes
3. Show how coding theory techniques are used in proving lower bounds for matrix multiplication.
4. Describe how error correcting codes are used in derandomization.