Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Nonlinear dimensionality reduction for faster kernel methods in machine learning.

Christopher Musco
Massachusetts Institute of Technology
February 12, 2018

The Random Fourier Features (RFF) method (Rahimi, Recht, NIPS 2007) is one of the most practically successful techniques for accelerating computationally expensive nonlinear kernel learning methods. By quickly computing a low-rank approximation for any shift-invariant kernel matrix, RFF can serve as a preprocessing step to generically accelerate algorithms for kernel ridge regression, kernel clustering, kernel SVMs, and other benchmark data analysis tools.
 

Outlier-Robust Estimation via Sum-of-Squares

Pravesh Kothari
February 6, 2018

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent works. We also show that the guarantees of our algorithms match information-theoretic lower-bounds for the class of distributions we consider. These better guarantees allow us to give improved algorithms for independent component analysis and learning mixtures of Gaussians in the presence of outliers.
 

Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound

Amnon Ta-Shma
Tel Aviv University
January 30, 2018

I will show an explicit construction of a binary error correcting code with relative distance $\frac{1-\epsilon}{2}$ and relative rate $\epsilon^{2+o(1)}$. This comes close to the Gilbert-Varshamov bound that shows such codes with rate $\epsilon^2$ exist, and theLP lower bound that shows rate $\frac{\epsilon^2}{\log \frac{1}{\epsilon}}$ is necessary. Previous explicit constructions had rate about$\epsilon^3$, and this is the first explicit construction to get that close to the Gilbert-Varshamov bound.

This talk will have two parts, on Monday and Tuesday.

Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound

Amnon Ta-Shma
Tel Aviv University
January 29, 2018

I will show an explicit construction of a binary error correcting code with relative distance $\frac{1-\epsilon}{2}$ and relative rate $\epsilon^{2+o(1)}$. This comes close to the Gilbert-Varshamov bound that shows such codes with rate $\epsilon^2$ exist, and theLP lower bound that shows rate $\frac{\epsilon^2}{\log \frac{1}{\epsilon}}$ is necessary. Previous explicit constructions had rate about$\epsilon^3$, and this is the first explicit construction to get that close to the Gilbert-Varshamov bound.

This talk will have two parts, on Monday and Tuesday.

A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Svensson
École polytechnique fédérale de Lausanne
January 23, 2018

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.

The Matching Problem in General Graphs is in Quasi-NC

Ola Svensson
École polytechnique fédérale de Lausanne
January 22, 2018

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in polylogarithmic time on quasi-polynomially many processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain a Randomized NC algorithm.

A PSPACE construction of a hitting set for the closure of small algebraic circuits

Amir Shpilka
Tel Aviv University
December 12, 2017

We study the complexity of constructing a hitting set for the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given nsr in unary outputs a set of inputs from of size poly(nsr), with poly(nsr) bit complexity, that hits all $n$-variate polynomials of degree $r$ that are the limit of size $s$ algebraic circuits.

Recent advances in high dimensional robust statistics

Daniel Kane
University of California, San Diego
December 11, 2017
It is classically understood how to learn the parameters of a Gaussian even in high dimensions from independent samples. However, estimators like the sample mean are very fragile to noise. In particular, a single corrupted sample can arbitrarily distort the sample mean. More generally we would like to be able to estimate the parameters of a distribution even if a small fraction of the samples are corrupted, potentially adversarially.