Harvard/MIT/MSR Reading Group

Mika Göös: Query-to-Communication Lifting Theorems
Friday, November 4, 2016 - 1:30pm to 4:30pm

Abstract:  I will discuss new lower bound methods in communication complexity that "lift" lower bounds from decision tree complexity.

Larry Guth: Decoupling Theorems in Fourier Analysis
Friday, October 28, 2016 - 1:30pm to 4:30pm

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

Sebastien Bubeck: Kernel-based methods for bandit convex optimization
Friday, October 21, 2016 - 1:30pm to 4:00pm
Abstract:  In bandit optimization one wants to optimize some unknown function using an approximate function value oracle.
David Zuckerman: Explicit Two-Source Extractors and Resilient Functions
Friday, April 15, 2016 - 1:30pm to 4:30pm

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)}.

Ron Rothblum: Constant-Round Interactive Proofs for Delegating Computation
Friday, April 8, 2016 - 1:30pm to 4:30pm


Alexander "Sasha" Rakhlin: A few peculiar connections between deterministic worst-case prediction algorithms and probabilistic inequalities
Friday, April 1, 2016 - 1:30pm to 4:30pm

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.

JM Landsburg: Geometry and the Complexity of Matrix Multiplication
Friday, March 11, 2016 - 1:30pm to 4:30pm

In 1969 Strassen discovered the standard algorithm for multiplying nxn matrices, that takes O(n^3) arithmetic operations, is not the best.

Julia Chuzhoy: Excluded Grid Theorem: Improved and Simplified
Friday, February 26, 2016 - 1:30pm to 4:30pm

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

Avi Wigderson: The Singularity of Symbolic Matrices
Friday, February 12, 2016 - 1:30pm to 4:30pm


The main object of study of this talk are matrices whose entries are linear forms in a set of formal variables (over some field).  The main problem is determining if a given such matrix is invertible or singular (over the appropriate field of rational functions).

Nikhil Srivastava: Ramanujan Graphs from Finite Free Convolutions
Friday, February 5, 2016 - 1:30pm to 4:30pm
Abstract:  We show that a random d-regular bipartite graph is an optimal (i.e.,
Ramanujan) expander with nonzero probability. Notably, we use tools


Subscribe to Harvard/MIT/MSR Reading Group