Elena Agliari (Università degli Studi di Parma)
“Diffusive Thermal Dynamics for the Ising model on the Erdös-Rényi random graph”
presentation
show abstract
hide abstract
We consider the Ising model on the Erdös-Rényi random graph when a diffusive thermal dynamics is applied. Such a dynamics is generated by a random walker diffusing throughout the sites of the underlying graph and possibly updating the relevant spin. The coupling between the random walker and the magnetic structure also biases the walk, which yields non-trivial effects on the thermodynamics properties of the system, as evidenced by means of Monte Carlo simulations.
Finally, we discuss the relevance of the diffusive dynamics in condensed matter and social systems.
Louis-Pierre Arguin (WIAS)
“Ultrametricity from Robust Stochastic Stability”
presentation
Joint work with M. Aizenman.
show abstract
hide abstract
The Aizenman-Sims-Starr principle expresses the free energy of a class of mean-field spin glass models as a variational principle over Random Overlap Structures or ROSt's. A ROSt is a probability measure on (ξ, Q) where ξ is a collection of weights and Q is a quadratic form giving the overlaps between weights. The approach suggests that the optimal ROSt's are stochastically stable, i.e. invariant under the cavity dynamics where the weights are evolved by gaussian variables correlated throughi Q. The class of stochastically stable ROSt's was conjectured, under some robustness conditions, to be exhausted by the Ruelle Probability Cascades, whose overlaps are ultrametric. We prove a version of this conjecture in the case where ξ is countable and the overlaps assume a finite number of values.
Adriano Barra (Università di Roma "La Sapienza")
“Exploring the rheology of soft glasses at a mesoscopic level.”
Joint work with Peter Sollich
show abstract
hide abstract
I will try to present a streamlined introduction to the phenomenology of complex rheology, a short overview on some numerical progress in our understanding of these systems and a comparison with predictions by the SGR model of Sollich. At a "mesoscopic" level these systems can be described as interacting trap-models driven by an external field (constant shear); once a steady state is achieved, they relax their stress forming networks of complex topology.
Chiara Basile
(University of Bologna)
“Similarity metrics based on n-gram statistics and applications to authorship attribution problems”
presentation
show abstract
hide abstract
I will describe a quantitative approach to authorship attribution of anonymous texts, based on on the so-called n-gram distance, a simple similarity metric which compares the distributions of subsequences of length n in the texts. An application of this method to the attribution of newspaper articles written by the Italian intellectual and politician Antonio Gramsci and his coworkers will be presented. Some theoretical aspects of the distance will then be discussed through multi-graph theory.
Alessandra Bianchi
(WIAS)
“Metastable exit times in the random field Curie-Weiss model.”
show abstract
hide abstract
We will discuss the metastable behavior of the random field Curie-Weiss model under Glauber dynamics. Using the potential theoretic approach , we will derive matching upper and lower bounds on capacities and metastable exit times, for any temperature and also in the case when the distribution of the random field is continuous.
Charles
Bordenave
(Université de Toulouse)
“Resolvent of large random graphs”
presentation
Joint work with Marc Lelarge
show abstract
hide abstract
We will analyze the convergence of the spectrum of large random graphs to the spectrum of a limit infinite graph. These results will be applied to graphs converging locally to trees and derive a new formula for the Stieljes transform of the spectral measure of such graphs. We illustrate our results on the uniform regular graphs, Erdos-Renyi graphs and preferential attachment graphs. We will sketch examples of application for weighted graphs, bipartite graphs and the uniform spanning tree of n vertices.
Anton
Bovier
(WIAS)
“Universality of Levy processes in ageing systems”
show abstract
hide abstract
I will discuss the appearance of $\alpha$-stable L'evy processes as universal mechanisms for ageing in a variety of models. I will emphasis the r\^ole played by extreme values theory in the analysis of these dynamics and show how classical methods already give rather surprising results for the dynamics of certain mean field spin glass models.
Raffaella Burioni (Università degli Studi di Parma)
“Interacting random walks in restricted and random geometries”
presentation
show abstract
hide abstract
We consider N walkers interacting through reaction-diffusion processes, modelling autocatalytic reactions and spreading-by-transfer phenomena. We derive analytical results in asymptotic regimes, which are strongly influenced by the geometry of the substrates where diffusion occurs.
We discuss an application to the case of information spreading efficiency, relevant in optimization of marketing strategies.
Lauren Caston (Rand Corporation)
“Statistical Mechanics and Behavioral Models”
show abstract
hide abstract
How do changes in local or global policy affect fundamentally uncertain phenomena? For example, what levers are available to social leaders that may help reduce crime or smoking in certain communities or populations? RAND, a U.S.-based nonprofit think tank, often seeks out practical solutions to such public policy-relevant questions by developing and employing mathematical models to help understand social behavior, resource management, and decision-making under deep uncertainty. One fundamental component of policy research is an individual?s or a group?s decision calculus, a concept that has developed through the last couple centuries; the notion of an expected value, risk analysis, game theory, and subjective probabilities mark various stages of this evolution. In this talk I will give a brief background of RAND, then review the current application of statistical mechanics models to the study of social trends. I will attempt to assess the potential impact such methods may have on policy, and therefore shed some light on their viability to continue the progression of economic and social modeling.
Nick Crawford (UC Berkeley)
“Central Limit Theorems for the Energy Density in the High Temperature phase of the Sherrington Kirkpatrick Model”
presentation
Joint work with Sourav Chatterjee
show abstract
hide abstract
In this talk we detail very recent results regarding the fluctuations of various quantities in the high temperature phase of the SK model. It is well known that the energy density is quite well behaved when the external field is set to $0$, having fluctuations of order one for all temperature above $T_c=1$. Comets and Neveau, and independently Chatterjee, show ''
affiliation 'by very different methods', that the energy density satisfies a quenched CLT in the limit as the volume tends to infinity. The general case was left open and it was not clear how to proceed. In this talk we resolve this problem, applying a combination of the cavity method and Stein's method, a powerful quantitative tool for proving CLT's. No prior knowledge of this technique is assumed.
Steffen Dereich (University of Bath)
“Degree evolutions in random networks with concave preferential attachment rule”
presentation
The talk is based on joint work with Peter Mörters
show abstract
hide abstract
In this talk we define a dynamic model of random networks, where new vertices are connected to old ones with a probability proportional to a sublinear function of their degree. We first give a strong limit law for the emprical degree distribution, and then have a closer look at the temporal evolution of the degrees of individual vertices, which will be described in terms of large and moderate deviation principles. Using these results, we expose an interesting phase transition: in cases of \emph{strong} preference of large degrees, eventually a single vertex emerges forever as vertex of maximal degree, whereas in cases of \emph{weak} preference, the vertex of maximal degree is changing infinitely often. The transition between the two phases occurs in the case when a new edge is attached to an existing vertex with a probability proportional to the root of its current degree.
Yogeshwaran Dhandapani (Ecole Normale Superieure Paris)
“Directionally Convex Ordering of Random Measures, Shot-Noise fields and some applications to wireless networks”
presentation
This is an on-going joint work with Francois Baccelli and Bartek Blaszczyszyn.
show abstract
hide abstract
In the standard stochastic geometric setting, wireless networks can be modeled as point processes and their performances as certain mean functionals of the point process. Obtaining closed form expressions of such functionals is not easy for a general class of point processes. This motivates a comparative study. We study comparison of one such class of mean functionals - the additive and extremal shot-noise fields - which arise naturally in modeling of wireless networks, as ingredients of the so called Signal-to-Interference-Noise-Ratio.
To analyze them more rigorously, we make a comparative study of random mesaures with point processes being nothing but random counting measures. Extensively using the theory of stochastic ordering, we show implications of this comparison on attraction or repulsion of points, shot-noise fields etc. Our interest is in similar point processes, point processes with same number of points on a average but differing variances',. To this end we shall give examples of such point processes. Such examples shall be discussed.
Federico Gallo
(Office of Climate Change)
“Avoiding dangerous climate change by inducing behaviour change”
show abstract
hide abstract
Discrete choice is an econometric tool that is routinely used to help decision making, both in the private and public sectors. This tool has been applied to problems in areas such as transport, healthcare and telecommunications.
A key weakness of discrete choice is that it does not account for herd behaviour. Currently, we are attempting to tackle this issue by introducing elements of statistical mechanics, the theory that describes phase transitions such as boiling water. This allows us to describe the critical thresholds or tipping points that are observed in mass behaviour.
As an important application, these models can contribute to solving the problem of climate change. In particular, energy efficiency is an area where the market has failed to exploit opportunities worth hundreds of billions of dollars worldwide. Discrete choice and statistical mechanics could help decision makers develop policies to avoid dangerous climate change by inducing behaviour change towards a less carbon intensive lifestyle.
Ignacio
Gallo (University of Bologna)
“A tentative analysis of an Ising model on the Erdös-Rényi random graph”
show abstract
hide abstract
I shall consider an Ising model on the Erdös-Rényi random graph. Two working assumptions about the model's factorization properties will be made in order to derive a proposal for a consistency equation for the system's magnetization.
Francesco
Guerra (University of Rome "La Sapienza)
“Probabilistic aspect of spin glass theory”
show abstract
hide abstract
We consider the Sherrington-Kirkpatrick mean field spin glass model, together with other disordered statistical models, as spin glass diluted models, the generalized random energy model, and ferromagnetic diluted models.
As it is very well known, all these models are described in terms of a functional order parameter, as was discovered by Giorgio Parisi many years ago.
We explain the general structure of these models, and investigate about the variables conjugated to the functional order parameter, in the frame of a new Lagrange variational principle.
CLAUDIO GIBERTI
(Università di Modena e Reggio Emilia)
“Overlap Equivalence and Ultrametricity in Short Range Spin
Glass"
presentation
Joint work
with: P.Contucci, C.Giardina', G.Parisi, C.Vernia
show abstract
hide abstract
We test the property of ultrametricity for three-dimensional Edwards-Anderson
model in zero magnetic field with numerical simulations up to $20^3$ spins. We
find an excellent agreement with the prediction of themean field theory. The
results are presented both for the link and for the standard overlap, which are
shown to be mutually non fluctuating quantities and, therefore, to be completely
equivalent in the description of the low temperature phase of the
Edwards-Anderson model.
Markus Heidenreich
(Eindhoven University of Technology)
“On mean-field behaviour of long- and finite-range Ising model”
presentation
Joint work with Remco van der Hofstad and Akira Sakai
show abstract
hide abstract
We consider the Ising model on the hypercubic lattice Z^d. Using Sakai's *lace expansion* for the Ising model, we show that the model exhibits *mean-field behaviour* in dimension d>4 for finite-variance spin-spin coupling and sufficient spread-out, and in dimension $d>2'' => '\alpha \wedge 2',$ if the spin-spin coupling has power law distribution with parameter $d+\alpha$.
Remco van der Hofstad (Eindhoven University of Technology)
“Universality of distances in random graphs”
presentation
Joint work with Gerard Hooghiemstra, Piet Van Mieghem, Dmitri Znamenski and Henri van den Esker
show abstract
hide abstract
The topological properties of complex networks have received enormous attention. Measurements have shown fascinating common features, such as power law degree sequences and the `small world phenomenon'. The small world phenomenon states that typical distances in large complex networks are small, while a complex network has a power law degree sequence when the number of vertices with degree proportional to k decays as an inverse power of k.
We discuss several models for complex networks where the number of vertices of the graph with degree k decays as an inverse power of k. Such models can either be static, i.e., of fixed size, or dynamic, i.e., growing with time. A much investigated static model is the configuration model, while dynamic models receiving substantial attention are preferential attachment models, where the growth favors vertices which already have high degree. We investigate distances in such graphs. Perhaps surprisingly, the results suggest that graph distances grow in a similar way for the models under consideration when they have similar degrees. This hints at a strong form of universality.
Nicola Kistler (Universität Zürich)
“Universal structures in mean field models for spin glasses”
presentation
show abstract
hide abstract
I shall introduce some simple models of spin glasses which are amenable to a complete analysis. The emphasis will be on issues such as the ultrametricity, the Derrida-Ruelle cascades, and the chaos property. Joint work with Erwin Bolthausen.
Anton Klimovsky (TU-Berlin)
“Estimates of Guerra's remainder term in the SK model with multidimensional spins.”
presentation
Joint work with A. Bovier (Berlin)
show abstract
hide abstract
We prove upper and lower bounds on the free energy in the Sherrington-Kirkpatrick
(SK), model with multidimensional spins using the comparison schemes of Aizenman-Sims-Starr and Guerra involving the generalised random energy model-inspired processes and Ruelle's probability cascades (RPC). For this purpose an abstract quenched large deviations principle of the Gärtner-Ellis type is obtained. We employ the properties of the RPC and the Bolthausen-Sznitman coalescent to derive Talagrand's representation of the Guerra remainder term for our model. Specialising to the case of the Gaussian a priori distribution we compute the free energy at any temperature.
Christof Kuelske (Rijksuniversiteit Groningen)
“On transforms of measures on graphs and the posterior metric”
presentation
Joint work with Alex Opoku
show abstract
hide abstract
There are many examples of simple transformations of Gibbs measures, on the lattice, on trees, on the complete graph, that are known to spoil the Gibbsian
property of various initial measures by creating long-range 'non-continuous', behavior of the conditional probabilities of the image systems.
How explicit can we control the continuity of conditional probabilities in the good cases when this is not true and the image measure IS actually Gibbs? We present a general method to derive continuity estimates for conditional probabilities of general 'possibly continuous-valued', spin models subjected to local transformations. Such systems arise in the study of a stochastic time-evolution of Gibbs measures, noisy observations, or local discretizations. A crucial step in our unifying approach is the good choice of a metric on the image space, as we will explain, namely the so-called posterior-metric.
Jorge Kurchan (ESPCI)
“Large deviations in transport models”
show abstract
hide abstract
A general theory for the large, smooth 'hydrodynamic', deviations of systems has been developed in the last few years by Bertini, De Sole, Gabrielli, Jona-Lasinio and Landim. It is formally very close to the Semiclassical approach to Quantum Mechanics, and it reduces the solution of the fluctuating system to that of finding trajectories of a Classical system.
When applied to several simple one-dimensional transport models driven out of equilibrium, it was found that a surprising sequence of transformations further yield an explicit solution of these Classical equations, thus reproducing exact result obtained previously by other means by Derrida et al, and Kipnis et al.
It turns that at the bottom of this miracle is the fact that these systems have the remarkable 'though specific', feature that a non-local tranformation maps the driven version into an undriven, equilibrium one.
Marc Lelarge (INRIA-ENS)
“Dynamic Programming Optimization over Random Data: the Scaling Exponent for Near-optimal Solutions”
presentation
Joint work with D. Aldous and C. Bordenave
show abstract
hide abstract
A very simple example of an algorithmic problem solvable by dynamic programming is to maximize, over sets A in {1,2,...,n}, the objective function |A| - \sum_i \xi_i 1'' => 'i \in A,i+1 \in A', for given \xi_i > 0. This problem, with random (\xi_i), provides a test example for studying the relationship between optimal and near-optimal solutions of combinatorial optimization problems. We show that, amongst solutions differing from the optimal solution in a small proportion \delta of places, we can find near-optimal solutions whose objective function value differs from the optimum by a factor of order \delta^2 but not smaller order. We conjecture this relationship holds widely in the context of dynamic programming over random data, and Monte Carlo simulations for the Kauffman-Levin NK model are consistent with the conjecture. This work is a technical contribution to a broad program initiated in Aldous-Percus (2003) of relating such scaling exponents to the algorithmic difficulty of optimization problems.
Marco Lenci (Università di Bologna)
“Recurrence for persistent random walks in two dimensions”
presentation
show abstract
hide abstract
I will discuss the question of recurrence for persistent 'or Newtonian', random walks in Z^2, i.e., random walks whose transition probabilities depend both on the walker's position and incoming direction. Combining results from probability theory and dynamical systems, recurrence can be proved for a large class of such processes, including all "invertible" walks in elliptic random environments. Furthermore, rewriting our Newtonian walks as ordinary random walks in a suitable graph, one can gain a better idea of the geometric features of the problem, and obtain further examples of recurrence.
Nelly Litvak
(University of Twente)
“Analysis of an on-line algorithm for page importance computation”
presentation
Joint work with Philippe Robert
show abstract
hide abstract
Many algorithms for ranking of Web pages such as Google PageRank assign importance scores according to a stationary distribution of a Markov random walk on the Web graph. Although in the classical search scheme the ranking scores are precomputed off-line, several challenging problems in contemporary Web search, such as personalized search and search in entity graphs, require on-line PageRank computation. In this work we analyze an original on-line algorithm proposed by Abiteboul, Preda and Cobena. In the beginning, each page receives an equal amount of cash, and every time when a page is visited by a random walk, it distributes its cash among its outgoing links. The PageRank score of a page is then proportional to the amount of cash transferred from this page. We model the cash distribution using a discrete cat-and-mouse process, where the cat performs the Markov random walk and the mouse makes a step only when hitted by the cat. We prove that the distribution of cash among the pages is characterized by the probability distribution of the mouse's position. Further, we consider several classical random walks of the cat and analyze the corresponding behavior of the mouse.
Malwina Luczak
(London School of Economics)
“A new approach to the giant component problem”
presentation
Joint work with Svante Janson.
show abstract
hide abstract
We study the largest component of a random 'multi',graph on $n$ vertices with a given degree sequence. We let $n$ tend to infinity. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability all the components are small, and other conditions that imply that with high probability there is a giant component and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the results by Molloy and Reed on the size of the largest component in a random graph with a given degree sequence.
We further obtain a new sharp result for the giant component just above the threshold, generalizing the case of $G'' => 'n,p',$ with $np=1+\omega(n)n^{-1/3}$, where $\omega (n)\to\infty$ arbitrarily slowly.
Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs.
Enzo Marinari
(Università di Roma "La Sapienza")
“An introduction to numerical studies of spin glasses, and some recent advances about finite size effects.”
presentation
show abstract
hide abstract
I will try to give the most important elements that allow effective numerical simulations of spin glasses and, in larger generalities, of complex and frustrated systems. I will discuss the physical features of the system that are relevant at these effects, and how one can design optimized numerical algorithms by using this knowledge. I will discuss, among others, about parallel tempering 'annealing like', Monte Carlo schemes, and I will relate their performances to the structure of the phase space. As a modern application I will discuss a numerical and analytic approach to determining finite size corrections in the Sherrington-Kirkpatrick mean field theory of spin glasses.
Satoshi Morita (Tokyo Institute of Technology)
“Convergence Conditions for Quantum Annealing”
show abstract
hide abstract
Quantum annealing is a novel algorithm to solve generic optimization problems by quantum dynamics. Quantum fluctuations enable the system to find the target optimal state more effectively than thermal fluctuations which are used in a classical method, simulated annealing. I will derive convergence conditions for quantum annealing represented by the transverse field Ising model. Quantum fluctuations are tuned by the transverse field and the time evolution follows the real-time Schroedinger equation. I will show that a power decay of the transverse field satisfies the adiabatic condition, that is, the system stays arbitrarily close to the instantaneous ground state, finally reaching the optimal state. It is remarkable that an essentially different type of dynamics, the quantum Monte Carlo dynamics, shares the same condition for convergence.
Hidetoshi Nishimori (Tokyo Institute of Technology)
“Quantum annealing”
show abstract
hide abstract
Quantum annealing is a generic algorithm for combinatorial optimization using the idea of quantum-mechanical time evolution. It makes use of quantum fluctuations, i.e. quantum tunneling, for phase-space search for the optimal state, instead of thermal fluctuations in simulated annealing. Quantum annealing is also deeply related with quantum computation. I will first show several examples in which performance is compared between quantum and simulated 'classical', annealing. Then I will derive sufficient conditions under which quantum annealing is guaranteed to converge to the optimal state, corresponding to the famous theorem of Geman and Geman for convergence of the stochastic processes of simulated annealing. Finally, several interesting aspects concerning the relation between quantum annealing and quantum computation, quantum adiabatic evolution in particular, will be elucidated.
Guilhem Semerjian (LPT-ENS)
“Approximate counting of large subgraphs in random graphs with statistical mechanics methods”
presentation
show abstract
hide abstract
Counting the number of distinct copies of a given pattern in a graph can be a difficult problem when the sizes of both the pattern and the graph get large. This talk will review statistical mechanics approaches to some instances of this problem, focusing in particular on the enumeration of the long circuits of a graph. The outcomes of these methods are conjectures on the typical number of such patterns in large random graphs, and heuristic algorithms for counting and constructing them.
Shannon Starr (University of Rochester)
“About Universality for the Viana-Bray Model”
presentation
show abstract
hide abstract
In an important work, Carmona and Hu proved universality for the Sherrington-Kirkpatrick model, showing that for general random coupling constants, whose distributions satisfy weak conditions, the limiting pressure is essentially the same as that obtained when the couplings are all Gaussian. With Brigitta Vermesi, we considered an analogous problem for the diluted mean-field spin glass known as the Viana-Bray model, which is another model where Guerra and Toninelli's interpolation arguments apply. I will talk about our findings.
Lenka Zdeborova (LPTMS, University Paris-Sud)
“Random subcubes as a toy model for constraint satisfaction problems”
presentation
Joint work with Thierry Mora.
show abstract
hide abstract
Many hard combinatorial problems, such as random satisfiability or random coloring, have been shown to reproduce some characteristic properties of glassy materials. In particular, it has been proved that the configurational landscapes of the hardest problems are made of many disconnected ergodic components, leading to rich phase diagrams. Here we present an exactly solvable random-subcube model inspired by the structure of hard constraint satisfaction and optimization problems. Our model reproduces the structure of the solution space of the random satisfiability and coloring problems, and undergoes the same phase transitions. Distance properties, and their relation to ergodicity, are studied. The model can also be generalized to define a continuous energy landscape useful for studying several aspects of glassy dynamics.
Riccardo Zecchina (ICTP)
“Statistical Mechanics of Steiner trees”
show abstract
hide abstract
The Minimum Weight Steiner Tree (MST) is an important combinatorial optimization problem that has applications in a wide range of fields. Here we discuss a general technique to mutate the imposed global connectivity constrain into a local ones that can be analyzed with cavity equation techniques. This approach provides a message-passing heuristic for finding Steiner Trees with given depth. We study the statistical properties of MSTs on random graphs of various types.