## Edward T. Cone Concert Talk

Listen to pianists Uri Caine and Mario Laginha discuss music with Institute Artist-in-Residence Derek Bermel.

Derek Bermel, Uri Caine, and Mario Laginha

December 5, 2011

Listen to pianists Uri Caine and Mario Laginha discuss music with Institute Artist-in-Residence Derek Bermel.

Menachem Magidor

Hebrew University

December 6, 2011

This is a survey talk about different attempts to deal with the very troubling phenomena of independence in Set Theory.

Will Eno

January 20, 2012

Michael Saks

Rutgers, The State University of New Jersey

January 23, 2012

In the file maintenance problem, n integer items from the set {1,....,r} are to be stored in an array of size m>=n . The items are presented sequentially in an arbitrary order and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item is stored before the next arrives. If rm then we may have to shift the location of stored items IN

Tom Spencer

Professor, School of Mathematics, Institute for Advanced Study

January 23, 2012

This talk will review some theorems and conjectures about phase transitions of interacting spin systems in statistical mechanics. A phase transition may be thought of as a change in a typical spin configuration from ordered state at low temperature to disordered state at high temperature. I will illustrate how the symmetry of a spin system plays a crucial role in its qualitative behavior. Of particular interest is the connection between supersymmetric statistical mechanics and the spectral theory of random band matrices.

Russell Impagliazzo

Institute for Advanced Study

January 24, 2012

Abstract

The P vs. NP problem has sometimes been unofficially paraphrased as asking whether

it is possible to improve on exhaustive search for such problems as Satisfiability, Clique,

Graph Coloring, etc. However, known algorithms for each of these problems indeed are

substantially better than exhaustive search, if still exponential. Furthermore, although a

polynomial-time algorithm for any one of these problems implies one for all of them, these

improved exponential algorithms are highly specific, and it is unclear what the limit of

improvement should be.

The P vs. NP problem has sometimes been unofficially paraphrased as asking whether

it is possible to improve on exhaustive search for such problems as Satisfiability, Clique,

Graph Coloring, etc. However, known algorithms for each of these problems indeed are

substantially better than exhaustive search, if still exponential. Furthermore, although a

polynomial-time algorithm for any one of these problems implies one for all of them, these

improved exponential algorithms are highly specific, and it is unclear what the limit of

improvement should be.

Vadim Kaloshin

Pennsylvania State University; Member, School of Mathematics, Institute for Advanced Study

January 25, 2012

There are indications that in the 80s Guillemin posed a question: If billiard maps are conjugate, can we say that domains are the same up to isometry?

On one side, we show that conjugacy of different domains can't be C^1 near the boundary. In particular, billiard maps of the circle and an ellipse are both analytically integrable, but not C^1 conjugate. On the other side, if conjugate near the boundary s smoother, then domains are the same up to isometry.

(This is joint work with A. Sorrentino.)

Boris Khesin

University of Toronto; Member, School of Mathematics, Institute for Advanced Study

January 25, 2012

We present a Hamiltonian framework for higher-dimensional vortex filaments (or membranes) and vortex sheets as singular 2-forms with support of codimensions 2 and 1, respectively, i.e. singular elements of the dual to the Lie algebra of divergence-free vector fields. It turns out that the localized induction approximation (LIA) of the hydrodynamical Euler equation describes the skew-mean-curvature flow on higher vortex filaments of codimension 2 in any any dimension, which generalizes the classical binormal, or vortex filament, equation in 3D.

San Vu Ngoc

University of Rennes, France

January 27, 2012

Avi Wigderson

Herbert H. Maass Professor, School of Mathematics, Institute for Advanced Study

January 31, 2012

The Resolution proof system is among the most basic and popular for proving propositional tautologies, and underlies many of the automated theorem proving systems in use today. I'll start by defining the Resolution system, and its place in the proof-complexity picture.