Unique and 2:2 Games, Grassmannians, and Expansion

Irit Dinur
Weizmann Institute of Science; Visiting Professor, School of Mathematics
November 20, 2019

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 hypercontractivity of the Grassmannian complex plays a key role.

Nonconvex Minimax Optimization

Chi Jin
Princeton University; Member, School of Mathematics
November 20, 2019

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 challenges in addition to those that already persist in nonconvex minimization problems. This talk will cover a set of new phenomena, open problems, and recent results in this emerging field.

Constraint Satisfaction Problems and Probabilistic Combinatorics I

Fotios Illiopoulos
Member, School of Mathematics
November 19, 2019

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 deep connections to statistical physics.

High Dimensional Expansion and Error Correcting Codes

Irit Dinur
Weizmann Institute of Science; Visiting Professor, School of Mathematics
November 19, 2019

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 only known such expanders are number-theoretic or group-theoretic.

The singular set in the fully nonlinear obstacle problem

Ovidiu Savin
Columbia University
November 18, 2019

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,\log^\eps}$-manifolds. This essentially recovers the regularity result obtained by Figalli-Serra when the operator is the Laplacian.

An isoperimetric inequality for the Hamming cube and some consequences

Jinyoung Park
Rutgers University
November 18, 2019

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 cubes, and later by Ellis for subsets of any size. Our inequality also plays a key role in a recent result on the asymptotic number of maximal independent sets in the cube. 

 

This is joint work with Jeff Kahn.