Video Lectures

A possible high level description of statistical learning is that it aims to learn about some unknown probability distribution ("environment”) from samples it generates ("training data”). In its most general form, assuming no prior knowledge and...

We study boosting algorithms under the assumption that the given weak learner outputs hypotheses from a class of bounded capacity. This assumption is inspired by the common convention that weak hypotheses are “rules-of-thumbs” from an “easy-to-learn...

Proof Complexity studies the length of proofs of propositional tautologies in various restricted proof systems. One of the most well-studied is the Cutting Planes proof system, which captures reasoning which can be expressed using linear...

We show that a topologically mixing C^\infty Anosov flow on a 3 dimensional compact manifold is exponential mixing with respect to any equilibrium measure with Holder potential. This is a joint work with Masato Tsujii.

We propose a new hierarchy of semidefinite programming relaxations for inference problems. As test cases, we consider the problem of community detection in block models. The vertices are partitioned into k communities, and a graph is sampled...

The factorization of Fourier coefficients of automorphic forms plays an important role in a wide range of topics, from the study of L-functions to the interpretation of scattering amplitudes in string theory. In this talk I will present a transfer...

Much real-world data is sampled at irregular intervals, but most time series models require regularly-sampled data. Continuous-time models address this problem, but until now only deterministic (ODE) models or linear-Gaussian models were efficiently...

In 1965, M. Kac proved that discs were uniquely determined by their Dirichlet (or, Neumann) spectra. Until recently, disks were the only smooth plane domains known to be determined by their eigenvalues. Recently, H. Hezari and I proved that ellipses...

We investigate the approximability of the following optimization problem, whose input is an n-by-n matrix A and an origin symmetric convex set C that is given by a membership oracle: "Maximize the quadratic form as x ranges over C." This is a rich...

A weighted graph H is a sparsifier of a graph G if H has much fewer edges than G and, in an appropriate technical sense, H "approximates" G. Sparsifiers are useful as compressed representations of graphs and to speed up certain graph algorithms. In...