Dorit Aharonov

Quantum Computation, the Jones polynomial, and the Potts model

I will explain a very intriguing connection between low dimensional topology, knot invariants, and quantum computation: It turns out that in some well defined sense, quantum computation is equivalent to certain approximations of the Jones polynomial. In Computer Science language: the approximation of the Jones polynomial at certain points is BQP complete. This means that:
  1. There is an efficient quantum algorithm to approximate the Jones polynomial of any given link, at certain roots of unity;
  2. The approximation of the Jones polynomial is the hardest problem a quantum computer can possibly solve;
  3. Shor's factoring algorithm can be presented as the approximation of the Jones polynomial of a certain link.
My goal is to explain those results, the core of which is the link between quantum computation and unitary representations of the beautiful pictorial object known as the Temperley Lieb algebra. If time permits, I will also discuss recent extensions of those results, which make use of non-unitary representations of the Temperley Lieb algebras, and provide algorithms for many more problems, including an additive approximation of the partition function of the q-state Potts model. The talk is based on several joint works with Arad, Eban, Jones and Landau, following works of Kitaev, Freedman, Larsen and Wang. No prior knowledge of quantum computation, topology, or physics, will be assumed.

Andrei Okounkov

Wave fronts on random surfaces

David Ruelle

Is there a general linear response theory for the steady states under physical time evolutions?

In nonequilibrium statistical mechanics close to equilibrium, the linear response of a statistical mechanics equilibrium state under a perturbation of the original dynamics is given by the Green-Kubo formula. Away from equilibrium we face the mathematical problem of obtaining a linear response theory for a general dynamical system. For such a general time evolution the observed steady states are believed to be described by so-called SRB measures, and linear response theory should describe the change of SRB measures under perturbations of the dynamics. We review the theory of SRB measures, what is known mathematically of their dependence on parameters (in particular, the differentiability question in relation with bifurcations for systems that are not uniformly hyperbolic) and the possible existence of a linear response formula. The lecture should be accessible to a general scientifically educated audience.

Uri Zwick


How far off the edge of the table can we reach by stacking n identical, homogeneous, frictionless blocks of length 1? A classical solution achieves an overhang of (1/2)H_n, where H_n=1/1+1/2+..+1/n is the n-th harmonic number. This solution is widely believed to be optimal. We show, however, that it is, in fact, exponentially far from optimality by constructing simple n-block stacks that achieve an overhang of cn^{1/3}, for some constant c>0. We also show, under reasonable assumptions, that larger overhangs are impossible.
Joint work with Mike Paterson, Yuval Peres, Mikkel Thorup and Peter Winkler.