Harvard/MIT/MSR Reading Group

Abstract: In the last few years, Jean Bourgain and Ciprian Demeter have proven a variety of striking ``decoupling'' theorems in Fourier analysis.  I think this is an important development in the subject.  I don't know any applications to the theory of computation, but there are applications in pa

Abstract: We explicitly construct an extractor for two independent sources on n bits,each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\Omega(1)}.

Abstract: In this talk, we will outline several equivalences between deterministic and probabilistic statements. First, we will argue that *existence* of deterministic online algorithms can be certified via certain probabilistic inequalities.

Abstract:  One of the key results in Robertson and Seymour's seminal work on graph
minors is the Excluded Grid Theorem. The theorem states that there is a
function f, such that for every positive integer g, every graph whose