Tue, 04 May 2010

14:30 - 15:30
L3

Independent sets in bipartite graphs and approximating the partition function of the ferromagnetic Potts model

Leslie Goldberg
(University of Liverpool)
Abstract

This talk considers the problem of sampling an independent set uniformly at random from a bipartite graph (equivalently, the problem of approximately counting independent sets in a bipartite graph). I will start by discussing some natural Markov chain approaches to this problem, and show why these lead to slow convergence. It turns out that the problem is interesting in terms of computational complexity – in fact, it turns out to be equivalent to a large number of other problems, for example, approximating the partition function of the “ferromagnetic Ising model’’ (a 2-state particle model from statistical physics) in the presence of external fields (which are essentially vertex weights). These problems are all complete with respect to approximation-preserving reductions for a logically-defined complexity class, which means that if they can be approximated efficiently, so can the entire class. In recent work, we show some connections between this class of problems and the problem of approximating the partition function of the ``ferromagnetic Potts model’’ which is a generalisation of the Ising model—our result holds for q>2 spins. (This corresponds to the approximation problem for the Tutte polynomial in the upper quadrant

above the hyperbola q=2.) That result was presented in detail at a recent talk given by Mark Jerrum at Oxford’s one-day meeting in combinatorics. So I will just give a brief description (telling you what the Potts model is and what the result is) and then conclude with some more recently discovered connections to counting graph homomorphisms and approximating the cycle index polynomial.

Mon, 07 Jun 2010

12:00 - 13:00
L3

The torsional conifold: fivebranes and the Klebanov-Strassler theory

Dario Martelli
(Kings College London)
Abstract
We study a gravity solution corresponding to fivebranes wrapped on the S^2 of the resolved conifold. By changing a parameter the solution continuously interpolates between the deformed conifold with flux and the resolved conifold with branes. Therefore, it displays a geometric transition, purely in the supergravity context. The solution is a simple example of torsional geometry and may be thought of as a non-Kahler analog of the conifold. By U-duality transformations we can add D3 brane charge and recover the solution in the form originally derived by Butti et al. This describes the baryonic branch of the Klebanov-Strassler theory. Far along the baryonic branch the field theory gives rise to a fuzzy two-sphere. This corresponds to the D5 branes wrapping the two-sphere of the resolved conifold in the gravity solution.
Mon, 24 May 2010

12:00 - 13:00
L3

String Theory and Many-Body Physics

Djordje Minic
(VirginiaTech)
Abstract
Recent theoretical advances in string theory relate in an unexpected way the physics of gravity in certain D dimensional space-times with the dynamics of quantum field theories living on the associated (D-1) dimensional space-time boundary. This unsuspected relationship offers a remarkable new tool for dealing with some outstanding problems in condensed matter physics. In the first part of the talk I aim to explain both the intuitive and technical underpinnings of these new developments. In the second half of the talk I will present some recent results on aging in systems far from equilibrium and also some new avenues for research in condensed matter physics which involve the interplay of gauge fields, membranes and many-body systems. In particular this last work opens up an exciting possibility for fundamentally new states of condensed matter.
Subscribe to L3