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

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.


Subscribe to Algorithms and Complexity Seminars