Algorithms and Complexity Seminars
 |
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. |
|
|
Richard Peng: Solving SDD Linear Systems in Nearly mlog1/2n Time Friday, September 12, 2014 - 4:00pm to 5:00pm |
|
|
Carol Wang: Explicit List-Decodable Subspace Codes with High Rate Wednesday, April 9, 2014 - 4:00pm to 5:00pm |
Pages
