Video Lectures

Minimax optimization, especially in its general nonconvex formulation, has found extensive applications in modern machine learning, in settings such as generative adversarial networks (GANs) and adversarial training. It brings a series of unique...

The unique games conjecture gives a very strong PCP theorem, which, if true, leads to a clean understanding of a broad family of approximation problems. We will describe recent progress on the conjecture and how certain type of expansion and...

High dimensional expansion generalizes edge and spectral expansion in graphs to higher dimensional hypergraphs or simplicial complexes. Unlike for graphs, it is exceptionally rare for a high dimensional complex to be both sparse and expanding. The...

The tasks of finding and randomly sampling solutions of constraint satisfaction problems over discrete variable sets arise naturally in a wide variety of areas, among them artificial intelligence, bioinformatics and combinatorics, and further have...

I will introduce an isoperimetric inequality for the Hamming cube and some of its applications. The applications include a “stability” version of Harper’s edge-isoperimetric inequality, which was first proved by Friedgut, Kalai and Naor for half...

For the Obstacle Problem involving a convex fully nonlinear elliptic operator, we show that the singular set of the free boundary stratifies. The top stratum is locally covered by a $C^{1,\alpha}$-manifold, and the lower strata are covered by $C^{1...

The PCP theorem says that any mathematical proof can be written in a special "PCP" format such that it can be verified, with arbitrarily high probability, by sampling only a few symbols in the proof. Hence the name, Probabilistically Checkable...

I will discuss the extreme eigenvalue distributions of adjacency matrices of sparse random graphs, in particular the Erd{\H o}s-R{\'e}nyi graphs $G(N,p)$ and the random $d$-regular graphs. For Erd{\H o}s-R{\'e}nyi graphs, there is a crossover in the...

The study of random matrix moments of moments has connections to number theory, combinatorics, and log-correlated fields. Our results give the leading order of these functions for integer moments parameters by exploiting connections with Gelfand...

Let Q be a non-degenerate indefinite quadratic form in d variables. In the mid 80's, Margulis proved the Oppenheim conjecture, which states that if d ≥ 3 and Q is not proportional to a rational form then Q takes values arbitrarily close to zero at...