Georgia Institute of Technology College of Sciences

We consider the #P complete problem of counting the number of independent sets in a given graph. Our interest is in understanding the effectiveness of the popular Belief Propagation (BP) heuristic. BP is a simple and iterative algorithm that is known to have at least one fixed point. Each fixed point corresponds to a stationary point of the Bethe free energy (introduced by Yedidia, Freeman and Weiss (2004) in recognition of Hans Bethe's earlier work (1935)). The evaluation of the Bethe Free Energy at such a stationary point (or BP fixed point) leads to the Bethe approximation to the number of independent sets of the given graph. In general BP is not known to converge nor is an efficient, convergent procedure for finding stationary points of the Bethe free energy known. Further, effectiveness of Bethe approximation is not well understood. As the first result of this paper, we propose a BP-like algorithm that always converges to a BP fixed point for any graph. Further, it finds an \epsilon approximate fixed point in poly(n, 2^d, 1/\epsilon) iterations for a graph of n nodes with max-degree d. As the next step, we study the quality of this approximation. Using the recently developed 'loop series' approach by Chertkov and Chernyak, we establish that for any graph of n nodes with max-degree d and girth larger than 8d log n, the multiplicative error decays as 1 + O(n^-\gamma) for some \gamma > 0. This provides a deterministic counting algorithm that leads to strictly different results compared to a recent result of Weitz (2006). Finally as a consequence of our results, we prove that the Bethe approximation is exceedingly good for a random 3-regular graph conditioned on the Shortest Cycle Cover Conjecture of Alon and Tarsi (1985) being true. (Joint work with Venkat Chandrasekaran, Michael Chertkov, David Gamarnik and Devavrat Shah)

The talk is based on the recent paper by M.Hairer, J.Mattingly, and M.Scheutzow with the same title.There are many Markov chains on infinite dimensional spaces whose one-step transition kernels are mutually singular when starting from different initial conditions. We give results which prove unique ergodicity under minimal assumptions on one hand and the existence of a spectral gap under conditions reminiscent of Harris' theorem. The first uses the existence of couplings which draw the solutions together as time goes to infinity. Such "asymptotic couplings" were central to recent work on SPDEs on which this work builds. The emphasis here is on stochastic differential delay equations.Harris' celebrated theorem states that if a Markov chain admits a Lyapunov function whose level sets are "small" (in the sense that transition probabilities are uniformly bounded from below), then it admits a unique invariant measure and transition probabilities converge towards it at exponential speed. This convergence takes place in a total variation norm, weighted by the Lyapunov function. A second aim of this article is to replace the notion of a "small set" by the much weaker notion of a "d-small set," which takes the topology of the underlying space into account via a distance-like function d. With this notion at hand, we prove an analogue to Harris' theorem, where the convergence takes place in a Wasserstein-like distance weighted again by the Lyapunov function. This abstract result is then applied to the framework of stochastic delay equations.

In these talks we will introduced the basic definitions and examples of presheaves, sheaves and sheaf spaces. We will also explore various constructions and properties of these objects.