School of Mathematics

Symplectic Dynamics Seminar: On Conjugacy of Convex Billiards

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.)

CSDM: A Tutorial on the Likely Worst-Case Complexities of NP-Complete Problems

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.

Members Seminar: The Role of Symmetry in Phase Transitions

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.

An Optimal Lower Bound for File Maintenance

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

An Isoperimetric Inequality for the Hamming Cube and Integrality Gaps in Bounded-Degree Graphs

Siavosh Benabbas
Institute for Advanced Study
November 21, 2011
In 1970s Paul Erdos asked the following question: Consider all the boolean strings of length n. Assume that one has chosen a subset S of the strings such that no two chosen strings are different in precisely n/4 (or its closest even integer) coordinates. How big can the set of chosen strings be? Erdos conjectured that the answer is small (in a precise sense) and put a $250 prize for a solution. In 1987 Frankl and Rodl proved a strong form of this conjecture showing that such a set has to be exponentially smaller than the set of all strings of length n.

Orientability and Open Gromov-Witten Invariants

Penka Georgieva
Princeton University
November 11, 2011

I will first discuss the orientability of the moduli spaces of J-holomorphic maps with Lagrangian boundary conditions. It is known that these spaces are not always orientable and I will explain what the obstruction depends on. Then, in the presence of an anti-symplectic involution on the target, I will give a construction of open Gromov-Witten disk invariants. This is a generalization to higher dimensions of the works of Cho and Solomon, and is related to the invariants defined by Welschinger