Event Title: OR
Speaker Last Name:    OR
Year: (yyyy)

Mathematics Colloquium


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


Back to current Colloquium List
Back to UM Math seminars page


Department of Mathematics   |   2074 East Hall   |  530 Church Street  
Ann Arbor, MI 48109-1043
Phone: 734.764-0335   |   Fax: 734.763-0937

The page last modified
Site errors should be directed to