Peter van Emde Boas: History of the van Emde Boas Trees Wednesday, March 18, 2015  3:30pm to 4:30pm The stratified tree, also called van Emde Boas tree, is a data structure implementing the full repertoire of instructions manipulating a single subset A of a finite ordered Universe U = [0 ... u1]. 

Jelani Nelson: The JohnsonLindenstrauss lemma is optimal for linear dimensionality reduction Wednesday, March 11, 2015  2:30pm to 3:30pm Abstract: For any n>1 and eps in (0,1/2), we show the existence of a poly(n) sized subset X of R^n such that any linear map from (X, l_2) to l_2^m with distortion 1+eps must have a target dimension satisfying m = Omega( min{ n, eps^{2} log n } ). The proof is simple, and all 

Michael Cohen: l_p Row Sampling by Lewis Weights Wednesday, March 4, 2015  4:00pm to 5:00pm Abstract: We give a simple algorithm to efficiently sample the rows of a matrix while preserving the pnorms of its product with vectors. Given an nbyd matrix A, we find with high probability and in input sparsity time an A' consisting of about d log d rescaled rows of A such that A x_1 i 

Eric Price: Tight bounds for learning a mixture of two Gaussians Wednesday, January 14, 2015  4:00pm to 5:00pm We consider the problem of identifying the parameters of an unknown mixture of two arbitrary ddimensional gaussians from a sequence of independent random samples. 

Talk: Coding for Interactive Communication Made Efficient and Easy (or "How to make conversations robust to noise.") Tuesday, December 23, 2014  4:00pm to 5:00pm Interactive coding schemes add redundancy to any interactive protocol (=conversation) such that it can be reliably performed over a noisy channel which corrupts any eps fraction of the transmitted symbols. 

Sepideh Mahabadi: Approximate Nearest Line Search in High Dimensions Thursday, December 11, 2014  4:00pm


Avishay Tal: Shrinkage of De Morgan Formulae by Spectral Techniques Thursday, October 23, 2014  2:30pm to 3:30pm We give a new and improved proof that the shrinkage exponent of De Morgan formulae is 2. 

Multidimensional ϵApproximate Agreement and Computability in Byzantine Systems Wednesday, September 24, 2014  4:00pm to 5:00pm This talk is divided in two parts. In the first part, we discuss a problem called multidimensional ϵapproximate agreement, which generalizes the traditional ϵapproximate agreement of Dolev, Lynch, Pinter, Stark, and Weihl of 1983/1986. 

Richard Peng: Solving SDD Linear Systems in Nearly mlog1/2n Time Friday, September 12, 2014  4:00pm to 5:00pm 

Carol Wang: Explicit ListDecodable Subspace Codes with High Rate Wednesday, April 9, 2014  4:00pm to 5:00pm 