Dimitris Achlioptas (UCSC/RACTI)
Title: The Lovasz Local Lemma as a Random Walk
Abstract: We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser’s entropic method proof of the Lovasz Local Lemma for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular our method works when the set of underlying objects is entirely unstructured, fully dispensing with the notion of variables. Similarly to Moser’s argument, the key point is that algorithmic progress is measured in terms of entropy rather than energy (number of violated constraints) so that termination can be established even under the proliferation of states in which every step of the algorithm (random walk) increases the total number of violated constraints.
Based on joint work with Fotis Iliopoulos (NTUA)

Victor Bapst (Frankfurt)
Title: The Condensation Phase Transition in Random Graph Coloring
Abstract: Based on a non-rigorous formalism called the ''cavity method'', physicists have made intriguing predictions on phase transitions in discrete structures. One of the most remarkable ones is that in problems such as random $k$-SAT or random graph $k$-coloring, very shortly before the threshold for the existence of solutions there occurs another phase transition called condensation. The existence of this phase transition seems to be intimately related to the difficulty of proving precise results on, e.g., the $k$-colorability threshold as well as to the performance of message passing algorithms. In random graph $k$-coloring, there is a precise conjecture as to the location of the condensation phase transition in terms of a distributional fixed point problem. In this talk I will outline a proof of this conjecture, provided that $k$ exceeds a certain constant $k_0$. (Joint work with A. Coja-Oghlan, S. Hetterich, F. Rassmann, D. Vilenchik).

Ton Coolen (Kings College London)
Title: New Approaches to Loopy Random Graph Ensembles
Abstract: Apart from some special cases, most of our present analytical tools to deal with stochastic processes on finitely connected graphs require these graphs to be locally tree-like. This talk reports on ongoing research into the statistical mechanics of large random graph ensembles with significant numbers of short loops, and processes taking place on such graphs. The emphasis and spirit will be on exploration of new methods, rather than on reporting conclusive results.

Charilaos Efthymiou (Frankfurt)
Title: MCMC Sampling Colourings and Independent Sets of $G(n,d/n)$ Near Uniqueness Threshold
Abstract: Sampling from the Gibbs distribution is a well studied problem in computer science as well as in statistical physics. In this work we focus on the $k$-colouring model and the hard-core model with fugacity $\lambda$ when the underlying graph is an instance of Erdös-Rényi random graph $G(n,d/n)$, where $d$ is fixed.
We use the Markov Chain Monte Carlo method for sampling from the aforementioned distributions. In particular, we consider Glauber (block) dynamics. We show a dramatic improvement on the bounds for rapid mixing in terms of the number of colours and the fugacity, respectively.
For both models the bounds we get are only within small constant factors from the conjectured ones by the statistical physicists.
We use Path Coupling to show rapid mixing. For $k$ and $\lambda$ in the range of our interest the technical challenge is to cope with the high degree vertices, i.e. vertices of degree much larger than the expected degree $d$. The usual approach to this problem is to consider block updates rather than single vertex updates for the Markov chain. Taking appropriately defined blocks the effect of high degree vertices diminishes. However devising such a block construction is a non trivial task.
We develop for a first time a weighting schema for the paths of the underlying graph. Vertices which belong to ''light'' paths, only, can be placed at the boundaries of the blocks. The tree-like local structure of $G(n,d/n)$ allows the construction of simple structured blocks.

Silvio Franz (Paris Sud)
Title: Phase Transition and Glassiness in Finite D XOR-SAT Models
Abstract: The problem of XOR-SAT on random graph is known to be glassy if the number of clauses M exceeds the number of variables N. The presence of metastable states affect both the thermodynamic and the dynamic properties at low temperature. In the limit case N=M while the thermodynamics is trivial and a static glassy phase is absent, the dynamics remains non-trivial and glassy. Newmann and Moore (NM) proposed a 2D XOR-SAT model with N=M that shows that glassy dynamics persists in finite dimension. This model has become a paradigmatic example of the dynamical facilitation mechanism typical of Kinetically Constrained Models (KCM) where glassyness where thermodynamics is trivial and glassyness is a pure dynamical effect.
In this contribution I would like to show that the NM model correspond to a marginal point in the space of models: as soon as new constraints are introduced, thermodynamics ceases to be trivial and phase transitions appear. In particular we introduce short range and long range (small world) interaction and we show that in both cases a phase transition is induced.

David Galvin (Notre Dame)
Title: Taxi Walks and the Hard Core Model on Z²
Abstract: I’ll talk about the independent set (hard core) model on the two dimensional integer grid, in which independent sets are chosen with probability proportional to $\lambda$ to the power of their size, where $\lambda > 0$ is a density parameter.
Simulations suggest that there is a critical value $\lambda_c \approx 3.796$, such that for $\lambda < \lambda_c$ a randomly chosen independent set is usually quite disordered, while for $\lambda > \lambda_c$ it is usually highly ordered. A lot of work has gone into finding lower bounds for $\lambda_c$, with the best result to date being Vera, Vigoda and Yang’s $\lambda_c \geq 2.48$. Little enough has been known in the other direction until recently. In this talk I’ll explain how, adding some innovations to a standard contour approach, we can get $\lambda_c \leq 5.37$. Along the way, we’ll take a taxi ride around Manhattan.
This is joint work with Antonio Blanca (U.C. Berkeley), Dana Randall (Georgia Tech.) and Prasad Tetali (Georgia Tech.).

David Gamarnik (MIT)
Title: Limits of Local Algorithms for Randomly Generated Constraint Satisfaction Problems
Abstract: We establish a fundamental barrier on the power of local algorithms to solve randomly generated constraint satisfaction problems, despite several conjectures put forward in the past. In particular, we refute a conjecture by Hatami, Lovasz and Szegedy regarding the power of local algorithms to find nearly largest independent sets in random regular graphs. Similarly, we show that a broad class of local algorithms including the so-called Belief Propagation and Survey Propagation algorithms, fails to find satisfying assignments in randomly generated constraint satisfaction problems outside of the regime where simple algorithms succeed, despite conjectures put forward by statistical physicists. Our negative results exploit fascinating geometry of optimal solutions in random graphs, which was first predicted by physicists heuristically and now is confirmed by rigorous methods. According to this picture, the solution space exhibits a clustering property whereby the feasible solutions tend to cluster according to the underlying Hamming distance. We show that success of local algorithms implies violation of such a clustering property thus leading to a contradiction.
Joint work with Madhu Sudan (Microsoft Research)

Leslie Ann Goldberg (Oxford)
Title: Phase Transitions and Hardness of Approximating Partition Functions
Abstract: This talk will basically be a survey, giving examples showing how phase transitions can be used to give hardness results for the problem of approximating partition functions.

Svante Janson (Uppsala)
Title: Patterns in Random Permutations Avoiding Another Pattern
Abstract: It is well-known that the number of occurences of a given pattern $\sigma$ in a random permutation is asymptotically normal; similarly, the numbers of occurences of two (or more) given permutations are jointly asymptotically normal. However, if we condition on the non-existence of a pattern $\tau$, the situation changes drastically. I will concentrate on the case of 132-avoiding permutations, where I can prove limit results showing that the number of occurences of a pattern $\sigma$ has a limiting distribution, which is non-normal. (It can be expressed as a functional of a Brownian excursion.) Moments can be found by recursion.
Both the limiting distribution and the normalizing factors depend on $\sigma$.

Mihyun Kang (TU-Graz)
Title: Phase Transition in the Size of the Largest Component in Random Hypergraphs
Abstract: We consider a random $k$-uniform hypergraph $\mathcal H^k(n,p)$ with vertex set $V:=\{1,\ldots, n\}$ in which each $k$-tuple of vertices is an edge with probability $p$ independently. For $1\leq j \leq k-1$, a $j$-element subset of $V$ is called a $j$-set. Two $j$-sets $J_1,J_2$ are said to be $j$-connected if there is a sequence $E_1,\ldots,E_\ell$ of hyperedges such that $J_1 \subseteq E_1$, $J_2\subseteq E_\ell$ and $|E_i \cap E_{i+1}| \ge j$ for each $i=1,\ldots,\ell-1$. The relation of being $j$-connected is an equivalence relation for $j$-sets, and the equivalence classes are called the $j$-components. We show that the existence of a 'giant' $j$-component of size $\Theta (n^j)$ undergoes a phase transition at probability $p_0=p_0(k,j) := \left(\left(\binom{k}{j}-1\right)\binom{n}{k-j}\right)^{-1}$. In addition, we determine the size of the largest $j$-component when $p=(1+\varepsilon)p_0$, where we require $n^{-1/3} \ll \varepsilon \ll 1$.
Joint work with Oliver Cooley and Christoph Koch.

Eyal Lubetzky (Microsoft)
Title:Cutoff for the Ising model: the effect of initial conditions
Abstract: We establish the cutoff phenomena for the Glauber dynamics of the Ising model on general graphs at high enough temperatures using a new tool of information percolation. We then consider the finer property of what is the effect of initial conditions, and show that some initial conditions lead to faster mixing times than others, and that a warm start is essentially twice faster than almost every deterministic starting configuration.

Joint work with Allan Sly.

Nicolas Macris (EPFL)
Title: New Bounds for Random Constraint Satisfaction Problems via Spatial Coupling
Abstract: We describe a general methodology for applying "spatial coupling" to constraint satisfaction problems (CSPs). Using an analysis based on the interpolation method on one hand and the cavity theory on the other hand, we provide predictions on the thresholds of the coupled models. We argue that spatially coupled CSPs are much easier to solve than standard CSPs while the satisfiability threshold of coupled and standard CSPs are the same. These features provide a new avenue for obtaining better, provable, algorithmic lower bounds on satisfiability thresholds of the standard (uncoupled) CSP models. This is illustrated with simple algorithms for solving coupled CSPs and we provide the necessary machinery to analyze such algorithms. As a consequence, we derive new lower bounds for the satisfiability threshold of standard random CSPs. As we will see, these lower bounds sometimes surpass the current best lower bounds in the literature.
This is joint work with D. Achlioptas, H. Hassani and R. Urbanke.

Mike Molloy (Toronto)
Title: Cores of random hypergraphs and clustering in random XOR-SAT
Abstract: We describe the solution clusters for random XOR-SAT. When the density is strictly greater than the clustering threshold, these clusters are very well understood. More recently, we are looking at the case where the density is equal to the clustering threshold plus o(1).

To do this, we analyze the k-core of a random hypergraph. For example, we study the number of iterations required to reach the k-core by repeatedly removing all vertices of degree less than k. When the density is strictly greater than the k-core threshold, it takes O(log n) iterations, but when the density is equal to the k-core threshold plus $O(n^{-\delta})$ then the number of iterations rises to roughly $O(n^{\delta/2})$ for $\delta < 1/2$.
This includes joint work with D. Achlioptas and with P. Gao. Some results were obtained independently by M. Ibrahimi, Y. Kanoria, M. Kraning, and A. Montanari.

Dana Randall (Georgia Tech)
Title: Sampling biased permutations and lattice structures
Abstract: We consider algorithms for sampling biased lattice paths and permutations, with applications to tile‐based self‐assembly, asymmetric exclusion processes, self‐organized lists, and biased card shuffling. We define two general classes of biased permutations and give the first proofs that the nearest neighbor chain is rapidly mixing for both. Our bounds rely on bijections between permutations, inversion tables, and asymmetric simple exclusion processes (ASEPs). In addition, we demonstrate that the chain is not always rapidly mixing by constructing an example that requires exponential time to converge to equilibrium. (Joint work with Prateek Bhakta, Sarah Miracle and Amanda Streib)

Oliver Riordan (Oxford)
Title: Counting Connected Hypergraphs via the Probabilistic Method
Abstract: For $n\ge r\ge 2$ and $0<p<1$, let $H^r_{n,p}$ be the random $r$-uniform hypergraph with vertex set $[n]=\{1,2,\ldots,n\}$ in which each of the $n\choose r$ possible hyperedges is present independently with probability $p$, and normalize by writing $ p=p(n)=\lambda (r-2)!n^{-r+1} $ where $\lambda=\lambda(n)$.
It is well known that $H^r_{n,p}$ undergoes a phase transition at $\lambda=1$ where a giant component first emerges, as shown by Erdös and Rényi in the graph case. For $\lambda>1$ constant, Behrisch, Coja-Oghlan and Kang not only found the asymptotic order of the giant component, but proved joint central and local limit theorems for its order (number of vertices) and size (number of edges). Their local limit result gives an asymptotic formula for the probability that the order and size take any pair of values in the 'typical' range, and easily translates back to an asymptotic formula for the number of connected hypergraphs with a given number of vertices and a given 'excess' or 'nullity' (roughly speaking, number of extra 'overlaps' compared to a tree) which is of the same order as the number of vertices.
As in the graph case, the situation when $\lambda\to 1$ from above is in many ways more delicate. In joint work with Béla Bollobás we have managed to extend the bivariate local limit result to the rest of the supercritical regime, i.e., when $\lambda(n)=1+\varepsilon(n)$ with $\varepsilon=o(1)$ and $\varepsilon^3n \to \infty$ . This leads to an asymptotic formula for the number of connected hypergraphs with a given number $n$ of vertices and given excess $\ell$, whenever $\ell=o(n)$ and $\ell \to \infty$. This formula generalizes one proved by Karoński and Łuczak in 1997 by direct enumerative methods; their result applies only when $\ell=o(\log n/\log\log n)$.

David Saad (Aston)
Title: Self-sustained Clusters in Spin Models and their Link to Ergodicity Breaking
Abstract: We study the entropy of self-sustained spin clusters in disordered systems, where in-cluster local fields are dominated by cluster spins and are therefore difficult to destabilise. Self-sustained spin clusters are shown to be analytically linked to ergodicity breaking in fully connected Ising and Sherrington-Kirkpatick (SK) models, relating the less understood spin space characteristics to the well understood macroscopic state space properties. This correspondence is established through the absence of clusters in the paramagnetic phase, the presence of one dominant cluster in the Ising ferromagnet, and the formation of a non-trivial profile of self-sustained clusters in the SK spin glass. Yet unobserved phenomena are also revealed such as a first order phase transition in cluster sizes in the SK ferromagnet. The analysis was carried out under the replica symmetric and one-step replica symmetry breaking ansatze and could be adapted to investigate other spin models.
Chi Ho Yeung, David Saad , Self-sustained Clusters and Ergodicity Breaking in Spin Models, Phys.Rev.E 88 032132, (2013)

Guilhem Semerjian (ENS, Paris)
Title: Minimal Contagious Sets in Random Regular Graphs
Abstract: Epidemic processes are dynamical evolutions of the states of the vertices of a graph, with contagion rules based on the state of the neighboring vertices. If the evolution of such processes starting from a random initial configuration is usually rather easy to study, they also give birth to many difficult inference and optimization problems, for instance finding the origin of the epidemy given a snapshot of its later evolution, or targetting some nodes to be vaccinated in order to minimize the spreading of the epidemy. We will consider another optimization problem, namely the determination of the minimal number of initially infected vertices that trigger the propagation of the epidemy to the whole graph, concentrating on the bootstrap percolation model, in which inactive sites become active if their number of active neighbors reach some threshold.
This problem can be recast under the form of a statistical mechanics model on a sparse random graph, for which the so-called cavity method can be applied. The basic ingredients of this method will be reviewed, as well as some results for this specific problem, including quantitative conjectures on the size of minimal contagious sets of random regular graphs.

Perla Sousi (Cambridge)
Title: Uniformity of the Late Points of Random Walk on $\mathbb{Z}_n^d$ for $d\geq 3$.
Abstract: Let $X$ be a simple random walk in $\mathbb{Z}_n^d$ and let $t_{\rm{cov}}$ be the expected amount of time it takes for $X$ to visit all of the vertices of $\mathbb{Z}_n^d$. For $\alpha\in (0,1)$, the set $\mathcal{L}_\alpha$ of $\alpha$-late points consists of those $x\in \mathbb{Z}_n^d$ which are visited for the first time by $X$ after time $\alpha t_{\rm{cov}}$. Oliveira and Prata (2011) showed that the distribution of $\mathcal{L}_1$ is close in total variation to a uniformly random set. The value $\alpha=1$ is special, because $|\mathcal{L}_1|$ is of order 1 uniformly in $n$, while for $\alpha<1$ the size of $\mathcal{L}_\alpha$ is of order $n^{d-\alpha d}$. In joint work with Jason Miller we study the structure of $\mathcal{L}_\alpha$ for values of $\alpha<1$. In particular we show that there exist $\alpha_0<\alpha_1 \in(0,1)$ such that for all $\alpha>\alpha_1$ the set $\mathcal{L}_\alpha$ looks uniformly random, while for $\alpha<\alpha_0$ it does not (in the total variation sense). In this talk I will try to explain the main ideas of our proof and what are the next steps in this direction.

Eric Vigoda (Georgia Tech)
Title: Inapproximability for Counting Colorings via Second Moment Analysis of Random Regular Graphs
Abstract: A remarkable connection has been established for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree D undergoes a phase transition that coincides with the statistical physics uniqueness/non-uniqueness phase transition on the infinite D-regular tree. Despite this clear picture for 2-spin systems, there is little known for multi-spin systems. We present analog of these inapproximability results for counting colorings. We prove that for even k, in the tree non-uniqueness region (which corresponds to k<D) there is no FPRAS to approximate the number of colorings for triangle-free D-regular graphs. A key in our work is the use of induced matrix norms to give a simple and generic analysis of the second moment for any spin system on random D-regular bipartite graphs.
This is joint work with Andreas Galanis (Georgia Tech/Oxford) and Daniel Stefankovic (Rochester).

Lutz Warnke (Cambridge)
Title: Phase Transitions in Achlioptas Processes
Abstract: In the Erdös-Rényi random graph process, starting from an empty graph, in each step a new random edge is added to the evolving graph. One of its most interesting features is the 'percolation phase transition': as the ratio of the number of edges to vertices increases past a certain critical density, the global structure changes radically, from only small components to a single giant component plus small ones.
In this talk we consider Achlioptas processes, which have become a key example for random graph processes with dependencies between the edges.
Starting from an empty graph these proceed as follows: in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. We discuss why, for a large class of rules, the percolation phase transition is qualitatively comparable to the classical Erdös-Rényi process.
Based on joint work with Oliver Riordan.

Riccardo Zecchina (Torino)
Title: A Message Passing Approach to Inverse Dynamical Problems
Abstract: We will discuss a message-passing approach to inverse problems in the context of irreversible dynamical processes.
Belief propagation algorithms for both deterministic and stochastic dynamical models will be presented.
Examples of applications which will be discussed range from the maximization of the spread of influence for linear threshold models to the zero patient problem in epidemics.
Work in collaborations with: F. Altarelli, A. Braunstein, L. Dall’Asta, A. Lage-Castellanos