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

Abstract:  We show that a random d-regular bipartite graph is an optimal (i.e.,
Ramanujan) expander with nonzero probability. Notably, we use tools

Abstract:  In profoundly influential works, Shannon and Huffman showed that if Alice
wants to send a message X to Bob, it's sufficient for her to send roughly
H(X) bits, where H denotes Shannon's entropy function. This means that

Abstract:  In his work on the Brescamp-Leib inequality, Barthe proved a remarkably simple and useful theorem on finite sets of points in R^d.

Abstract: An EXIT function measures the ``response’’ of a code to
a particular channel. The area theorem refers to the fact that if you
integrate this function over a family of channels (from perfect channel