*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
