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 Abstract:
	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 Abstract: 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

Pages