Abstract:

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 connections between the two seemingly
unrelated areas were found. In this talk I will 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:
   i. Show that there are no good locally testable cyclic codes
   ii. Generalization of known constructions of locally testable codes
3. Define the new notion of "matrix codes" and show how coding theory
   techniques are used in proving lower bounds for matrix multiplication. 
4. Describe how matrix codes are related to derandomization.