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

We 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: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


Subscribe to Algorithms and Complexity Seminars