Title: The power and weakness of randomness (when you are short on time)
Abstract:
Man has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I'll describe two main aspects of this research on randomness, demonstrating respectively its power and weakness for making algorithms faster. I will address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs.
This is a joint ARC-SoM colloquium, and is in conjunction with the ARC Theory Day on November 11, 2011
4:30 pm - Klaus 1116 E & W
Title: Local correction of codes and Euclidean Incidence Geometry
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 algebraic and analytic tools.
Joint work with Boaz Barak, Zeev Dvir and Amir Yehudayoff
Avi Wigderson Lecture Video.
