|Date: Tuesday, March 10, 2015
Title: List decodability of structured random codes
Abstract: Suppose that a sender (Alice) wants to send a message to a receiver (Bob). The catch is that the message may get corrupted on the way to Bob. The theory of error correcting codes addresses this: Alice will encode her message (introducing some redundancy) so that Bob can tell what she meant to say even with corruption. One common encoding scheme is Reed-Solomon encoding, where Alice treats her message as a polynomial over a finite field and sends Bob some evaluations of this polynomial. Reed-Solomon codes are well-studied, but some of their combinatorial properties are still not well understood. In this talk, I'll address one such property, called list-decodability: this property is related to Alice and Bob's communication problem, and beyond that has many connections to complexity theory. I'll describe some recent results establishing the list-decodability of Reed-Solomon codes beyond the Johnson bound (a natural bound beyond which previous approaches do not work). Along the way, we'll develop some machinery for establishing the list-decodability for general ensembles of random codes; time permitting, I'll mention a few more applications. This is joint work with Atri Rudra.
Speaker: Mary Wootters
Institution: Carnegie Mellon