# Algorithms and Complexity Seminars

 Henry Yuen: Parallel repetition for entangled games via fast quantum searchWednesday, April 15, 2015 - 4:00pm to 5:00pmWe give improved parallel repetition theorems for multiplayer, one-round games with entangled players, when the inputs to the players are uncorrelated. Grigory Yaroslavtsev:Near Optimal LP Rounding for Correlation Clustering on Complete Graphs Thursday, April 9, 2015 - 3:15pm to 4:15pmIntroduced about 10 years ago by Bansal, Blum and Chawla, correlation clustering has become one of the standard techniques in machine learning and data mining. This due to several advantages of correlation clustering as compared to other standard clustering methods (e.g. k-means): Peter van Emde Boas: History of the van Emde Boas TreesWednesday, March 18, 2015 - 3:30pm to 4:30pmThe 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 ... u-1]. Jelani Nelson: The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reductionWednesday, 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:00pmAbstract:  We give a simple algorithm to efficiently sample the rows of a matrix while preserving the p-norms of its product with vectors.  Given an n-by-d 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 GaussiansWednesday, January 14, 2015 - 4:00pm to 5:00pmWe consider the problem of identifying the parameters of an unknown mixture of two arbitrary d-dimensional 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:00pmInteractive 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:00pmWe consider the Approximate Nearest Line Search (NLS) problem. Avishay Tal: Shrinkage of De Morgan Formulae by Spectral Techniques Thursday, October 23, 2014 - 2:30pm to 3:30pmWe 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:00pmThis 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.