Points, lines, and local correction of codes

-
Avi Wigderson, IAS
Fine Hall 224

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 (and related ones), which are motivated from questions about locally correctable codes and matrix rigidity. The proofs use an interesting combination of combinatorial, algebraic and analytic tools. The talk is self contained. Joint work with Boaz Barak, Zeev Dvir and Amir Yehudayoff