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.

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.

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.

Deforming Holomorphic Chern-Simons at Large N

Si Li
Member, School of Natural Sciences, IAS; Tsinghua University
November 15, 2019

We describe the coupling of holomorphic Chern-Simons theory at large N with Kodaira-Spencer gravity. This gives a complete description of open-closed string field theory in the topological B-model. We explain an anomaly cancellation mechanism at all loops in perturbation theory in this model. At one loop this anomaly cancellation is analogous to the Green-Schwarz mechanism. This is joint work with Kevin Costello.