Algorithms and Complexity Seminars
 |
Henry Yuen: Parallel repetition for entangled games via fast quantum search Wednesday, April 15, 2015 - 4:00pm to 5:00pm We 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:15pm Introduced 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 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 ... u-1]. |
|
|
Jelani Nelson: The Johnson-Lindenstrauss 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 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 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 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: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. |
Pages
