============================== Bar-Ilan Combinatorics Seminar ============================== The next meeting of the seminar this year will take place, IYH, on (when) Tuesday, 16 Tevet (Dec. 25) refreshments at 11:45, talk at 12:00 noon (where) Room 331 (Math Dept Seminar Room), Math and CS Building (216), Bar-Ilan University (who) Eli Ben-Sasson (Technion) will talk about (what) "Subspace polynomials and list decoding of Reed-Solomon codes" Abstract: --------- We will give a brief survey of notable results from the past decade regarding list decoding of Reed-Solomon codes. Then we will present our recent results regarding combinatorial limitations to list decoding of these codes. (This part is joint work with Swastik Kopparty and Jaikumar Radhakrishnan.) Our talk revolves around the following pair of questions. Let F be a finite field, |F|=n and kF, let List(f,k,A) be the set of polynomials of degree at most k over F that "intersect" f at least A times. (We say f "intersects" g at point x_0 iff f(x_0)=g(x_0).) 1) How large is List(f,k,A)? (This is known as the "combinatorial" list decoding problem) 2) If the list is small (say, polynomial in n), can all elements in it be found efficiently? Forthcoming Events ================== * 23 Tevet (Jan. 1) --- no meeting --- Representation Theory Conference - see * 1 Shvat (Jan. 8) Nathan Keller (Hebrew University): "On the correlation of monotone functions on the discrete cube" ************************************************************************* You are all invited ! (Graduate students especially welcome) If you want to give a talk at the seminar, or know a prospective speaker, please contact Ron Adin . Seminar's homepage: see *************************************************************************