[Colloquium] Show and Tell Series at TTI-C (Tuesday 9/6/05 @ 12:15)

[Katherine Cumming]

TTI-C SHOW AND TELL SERIES

Presented by:  Toyota Technological Institute at Chicago


Speaker: Eli Ben-Sasson, TTI-C
Speaker's home page: http://www.tti-c.org//ben-sasson.html

Time: Tuesday, September 6th, 2005
Location: TTI-C Conference Room
Lunch Provided @ 12:00pm 
Seminar @ 12:15pm

Title: Bounds for Combinatorial List Decoding of Reed-Solomon Codes


Abstract: 

*Question:* Given n points (x_1, y_1), ..., (x_n, y_n ) with distinct
x_i 's, what's the maximal number of distinct polynomials of degree at
most n^{0.7} that touch at least n^{0.8}of these points?

This question is tightly connected to fundamental problems in the theory
of Error Correcting Codes, such as **list decoding** of Reed-Solomon
codes and the tightness of the **Johnson Bound** for these codes.

In this talk we will discuss the problem and present some recent
progress regarding it

We assume only knowledge of basic linear algebra. In particular, we'll
explain, among other things, the meaning of list decoding and the
Johnson Bound.

(Answer to Question: The number is (in certain cases) super-polynomial
in n). 



-----------------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.  For information on
future TTI-C talks or events, please go to the TTI-C Events page,
http://www.tti-c.org/events.html.  TTI-C (1427 East 60th Street,
Chicago, IL  60637)