Locality in Error Correcting Codes

In the traditional set-up for error-correcting codes, a sender (Alice) wants to send a message to a receiver (Bob); the catch is that some errors may get introduced along the way. One solution to their problem is an error-correcting code. Alice will encode her message, introducing some redundancy, and send the resulting codeword to Bob; even if errors are introduced, the extra redundancy will allow Bob to recover the original message. While originally introduced for the purpose of communication, error-correcting codes have found many uses beyond Alice and Bob.  One feature of an error-correcting code which has been especially useful is that of *locality:* If Bob only wants part of Alice’s message, must he look at the entire codeword?  It turns out that, no, he needn’t, and moreover, this fact has been very useful in many application domains, including complexity theory, cryptography, and storage. In this talk, I’ll discuss different notions of locality in coding theory, and their many applications.  I’ll also talk about some recent work on one notion of locality—repair bandwidth—which is useful for distributed storage.