DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Brian Nakamura, Rutgers University, bnaka {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Local correction of codes and Euclidean Incidence Geometry

Speaker: Avi Wigderson, Institute for Advanced Study

Date: Thursday, December 1, 2011 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

A classical theorem in Euclidean geometry asserts that if a set of points has the property that every line through two of them contains a third point, then they must all be on the same line. We prove several approximate versions of this theorem, which are motivated from questions about locally correctable codes and matrix rigidity. The proofs use an interesting combination of combinatorial, algebraic and analytic tools.

(Joint work with Boaz Barak, Zeev Dvir and Amir Yehudayoff)

See: http://www.math.rutgers.edu/~bnaka/expmath/