Anfang der weitergeleiteten E-Mail:
Von: Robin Moser robin-mise@inf.ethz.ch Datum: 9. Oktober 2011 14:12:54 MESZ An: mise@inf.ethz.ch Betreff: [Mise] Mittagsseminar, October 10, Amir Shpilka (Technion)
Dear mittagsseminarists,
it is my pleasure to invite you to the following talk:
(! note that this talk takes place on a Monday)
Monday, October 10 Time: 12:15 pm Location: CAB G51
Amir Shpilka (Technion): Tight lower bounds for 2-query LCCs over finite fields
Abstract: A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic self-correcting algorithm that, with high probability, can correct any coordinate of the codeword by looking at only a few other coordinates, even if a fraction \delta of the coordinates are corrupted. In this talk we will show interesting connections between LCCs and questions in additive combinatorics, combinatorial geometry over finite fields and rank of design matrices. In particular, we will prove tight lower bounds on the length of 2-query LCCs over finite fields. This is a joint work with Arnab Bhattacharyya, Zeev Dvir and Shubhangi Saraf.