Mika Göös: QuerytoCommunication 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: Kernelbased 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 TwoSource 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 minentropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{\Omega(1)}. 

Ron Rothblum: ConstantRound Interactive Proofs for Delegating Computation Friday, April 8, 2016  1:30pm to 4:30pm Abstract: 

Alexander "Sasha" Rakhlin: A few peculiar connections between deterministic worstcase 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 

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

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