Seminars

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...

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...

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...

The current successes of deep neural networks have largely come on classification problems, based on datasets containing hundreds of examples from each category. Humans can easily learn new words or classes of visual objects from very few examples...

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...

Proof complexity studies the problem computer scientists and mathematicians face every day: given a statement, how can we prove it? A natural and well-studied question in proof complexity is to find upper and lower bounds on the length of the...

A martingale is a sequence of random variables that maintain their future expected value conditioned on the past. A $[0,1]$-bounded martingale is said to polarize if it converges in the limit to either $0$ or $1$ with probability $1$. A martingale...

Geometric Complexity Theory (GCT) was developed by Mulmuley and Sohoni as an approach towards the algebraic version of the P vs NP problem, VP vs VNP, and, more generally, proving lower bounds on arithmetic circuits. Exploiting symmetries, it...

This talk is going to be an extended and more technical version of my brief public lecture https://www.ias.edu/ideas/2017/arora-zemel-machine-learningI will present some of the basic ideas of machine learning, focusing on the mathematical...

A fundamental problem in Bayesian statistics is sampling from distributions that are only specified up to a partition function (constant of proportionality). In particular, we consider the problem of sampling from a distribution given access to the...