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 ReedSolomon encoding, where Alice treats her message as a polynomial over a finite field and sends Bob some evaluations of this polynomial. ReedSolomon codes are wellstudied, but some of their combinatorial properties are still not well understood. In this talk, I'll address one such property, called listdecodability: 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 listdecodability of ReedSolomon 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 listdecodability 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
