BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Fabio Martinelli

Fabio Martinelli appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath-phmath.MPcond-mat.stat-mechmath.COCryptography and SecurityFormal Languages and Automata Theoryastro-ph.SRcond-mat.dis-nnData Structures and AlgorithmsDiscrete MathematicsDistributed, Parallel, and Cluster ComputingLogic in Computer ScienceProgramming Languages

Catalog footprint

What is connected

38works
14topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

38 published item(s)

preprint2021arXiv

Coalescing and branching simple symmetric exclusion process

Motivated by kinetically constrained interacting particle systems (KCM), we consider a reversible coalescing and branching simple exclusion process on a general finite graph $G=(V,E)$ dual to the biased voter model on $G$. Our main goal are tight bounds on its logarithmic Sobolev constant and relaxation time, with particular focus on the delicate slightly supercritical regime in which the equilibrium density of particles tends to zero as $|V|\rightarrow \infty$. Our results allow us to recover very directly and improve to $\ell^p$-mixing, $p\ge 2$, and to more general graphs, the mixing time results of Pillai and Smith for the Fredrickson-Andersen one spin facilitated (FA-$1$f) KCM on the discrete $d$-dimensional torus. In view of applications to the more complex FA-$j$f KCM, $j>1$, we also extend part of the analysis to an analogous process with a more general product state space.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Diffusive scaling of the Kob-Andersen model in $\mathbb{Z}^d$

We consider the Kob-Andersen model, a cooperative lattice gas with kinetic constraints which has been widely analyzed in the physics literature in connection with the study of the liquid/glass transition. We consider the model in a finite box of linear size $L$ with sources at the boundary. Our result, which holds in any dimension and significantly improves upon previous ones, establishes for any positive vacancy density $q$ a purely diffusive scaling of the relaxation time $T_{\rm rel}$ of the system. Furthermore, as $q\downarrow 0$ we prove upper and lower bounds on $L^{-2} T_{\rm rel} (q,L)$ which agree with the physicists belief that the dominant equilibration mechanism is a cooperative motion of rare large droplets of vacancies. The main tools combine a recent set of ideas and techniques developed to establish universality results for kinetically constrained spin models, with methods from bootstrap percolation, oriented percolation and canonical flows for Markov chains.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Relaxation to equilibrium of generalized East processes on ${\mathbb{Z}}^d$: Renormalization group analysis and energy-entropy competition

We consider a class of kinetically constrained interacting particle systems on ${\mathbb{Z}}^d$ which play a key role in several heuristic qualitative and quantitative approaches to describe the complex behavior of glassy dynamics. With rate one and independently among the vertices of ${\mathbb{Z}}^d$, to each occupation variable $η_x\in\{0,1\}$ a new value is proposed by tossing a $(1-q)$-coin. If a certain local constraint is satisfied by the current configuration the proposed move is accepted, otherwise it is rejected. For $d=1$, the constraint requires that there is a vacancy at the vertex to the left of the updating vertex. In this case, the process is the well-known East process. On ${\mathbb{Z}}^2$, the West or the South neighbor of the updating vertex must contain a vacancy, similarly, in higher dimensions. Despite of their apparent simplicity, in the limit $q\searrow0$ of low vacancy density, corresponding to a low temperature physical setting, these processes feature a rather complicated dynamic behavior with hierarchical relaxation time scales, heterogeneity and universality. Using renormalization group ideas, we first show that the relaxation time on ${\mathbb{Z}}^d$ scales as the $1/d$-root of the relaxation time of the East process, confirming indications coming from massive numerical simulations. Next, we compute the relaxation time in finite boxes by carefully analyzing the subtle energy-entropy competition, using a multiscale analysis, capacity methods and an algorithmic construction. Our results establish dynamic heterogeneity and a dramatic dependence on the boundary conditions. Finally, we prove a rather strong anisotropy property of these processes: the creation of a new vacancy at a vertex $x$ out of an isolated one at the origin (a seed) may occur on (logarithmically) different time scales which heavily depend not only on the $\ell_1$-norm of $x$ but also on its direction.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Upper triangular matrix walk: Cutoff for finitely many columns

We consider random walk on the group of uni-upper triangular matrices with entries in $\mathbb{F}_2$ which forms an important example of a nilpotent group. Peres and Sly (2013) proved tight bounds on the mixing time of this walk up to constants. It is well known that the single column projection of this chain is the one dimensional East process. In this article, we complement the Peres-Sly result by proving a cutoff result for the mixing of finitely many columns in the upper triangular matrix walk at the same location as the East process of the same dimension. Moreover, we also show that the spectral gaps of the matrix walk and the East process are equal. The proof of the cutoff result is based on a recursive argument which uses a local version of a dual process appearing in Peres and Sly (2013), various combinatorial consequences of mixing and concentration results for the movement of the front in the one dimensional East process.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Dynamics of Lattice Triangulations on Thin Rectangles

We consider random lattice triangulations of $n\times k$ rectangular regions with weight $λ^{|σ|}$ where $λ>0$ is a parameter and $|σ|$ denotes the total edge length of the triangulation. When $λ\in(0,1)$ and $k$ is fixed, we prove a tight upper bound of order $n^2$ for the mixing time of the edge-flip Glauber dynamics. Combined with the previously known lower bound of order $\exp(Ω(n^2))$ for $λ>1$ [3], this establishes the existence of a dynamical phase transition for thin rectangles with critical point at $λ=1$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Mixing time and local exponential ergodicity of the East-like process in $\mathbf Z^d$

The East process, a well known reversible linear chain of spins, represents the prototype of a general class of interacting particle systems with constraints modeling the dynamics of real glasses. In this paper we consider a generalization of the East process living in the d-dimensional lattice and we establish new progresses on the out- of-equilibrium behavior. In particular we prove a form of (local) exponential ergodicity when the initial distribution is far from the stationary one and we prove that the mixing time in a finite box grows linearly in the side of the box.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the probability of staying above a wall for the (2+1)-dimensional SOS model at low temperature

We obtain sharp asymptotics for the probability that the (2+1)-dimensional discrete SOS interface at low temperature is positive in a large region. For a square region $Λ$, both under the infinite volume measure and under the measure with zero boundary conditions around $Λ$, this probability turns out to behave like $\exp(-τ_β(0) L \log L )$, with $τ_β(0)$ the surface tension at zero tilt, also called step free energy, and $L$ the box side. This behavior is qualitatively different from the one found for continuous height massless gradient interface models.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Random lattice triangulations: Structure and algorithms

The paper concerns lattice triangulations, that is, triangulations of the integer points in a polygon in $\mathbb{R}^2$ whose vertices are also integer points. Lattice triangulations have been studied extensively both as geometric objects in their own right and by virtue of applications in algebraic geometry. Our focus is on random triangulations in which a triangulation $σ$ has weight $λ^{|σ|}$, where $λ$ is a positive real parameter, and $|σ|$ is the total length of the edges in $σ$. Empirically, this model exhibits a "phase transition" at $λ=1$ (corresponding to the uniform distribution): for $λ<1$ distant edges behave essentially independently, while for $λ>1$ very large regions of aligned edges appear. We substantiate this picture as follows. For $λ<1$ sufficiently small, we show that correlations between edges decay exponentially with distance (suitably defined), and also that the Glauber dynamics (a local Markov chain based on flipping edges) is rapidly mixing (in time polynomial in the number of edges in the triangulation). This dynamics has been proposed by several authors as an algorithm for generating random triangulations. By contrast, for $λ>1$ we show that the mixing time is exponential. These are apparently the first rigorous quantitative results on the structure and dynamics of random lattice triangulations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Semiring-based Specification Approaches for Quantitative Security

Our goal is to provide different semiring-based formal tools for the specification of security requirements: we quantitatively enhance the open-system approach, according to which a system is partially specified. Therefore, we suppose the existence of an unknown and possibly malicious agent that interacts in parallel with the system. Two specification frameworks are designed along two different (but still related) lines. First, by comparing the behaviour of a system with the expected one, or by checking if such system satisfies some security requirements: we investigate a novel approximate behavioural-equivalence for comparing processes behaviour, thus extending the Generalised Non Deducibility on Composition (GNDC) approach with scores. As a second result, we equip a modal logic with semiring values with the purpose to have a weight related to the satisfaction of a formula that specifies some requested property. Finally, we generalise the classical partial model-checking function, and we name it as quantitative partial model-checking in such a way to point out the necessary and sufficient conditions that a system has to satisfy in order to be considered as secure, with respect to a fixed security/functionality threshold-value.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Cutoff for the East process

The East process is a 1D kinetically constrained interacting particle system, introduced in the physics literature in the early 90's to model liquid-glass transitions. Spectral gap estimates of Aldous and Diaconis in 2002 imply that its mixing time on $L$ sites has order $L$. We complement that result and show cutoff with an $O(\sqrt{L})$-window. The main ingredient is an analysis of the front of the process (its rightmost zero in the setup where zeros facilitate updates to their right). One expects the front to advance as a biased random walk, whose normal fluctuations would imply cutoff with an $O(\sqrt{L})$-window. The law of the process behind the front plays a crucial role: Blondel showed that it converges to an invariant measure $ν$, on which very little is known. Here we obtain quantitative bounds on the speed of convergence to $ν$, finding that it is exponentially fast. We then derive that the increments of the front behave as a stationary mixing sequence of random variables, and a Stein-method based argument of Bolthausen ('82) implies a CLT for the location of the front, yielding the cutoff result. Finally, we supplement these results by a study of analogous kinetically constrained models on trees, again establishing cutoff, yet this time with an $O(1)$-window.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Dynamics of $(2+1)$-dimensional SOS surfaces above a wall: Slow mixing induced by entropic repulsion

We study the Glauber dynamics for the $(2+1)\mathrm{D}$ Solid-On-Solid model above a hard wall and below a far away ceiling, on an $L\times L$ box of $\mathbb{Z}^2$ with zero boundary conditions, at large inverse-temperature $β$. It was shown by Bricmont, El Mellouki and Fröhlich [J. Stat. Phys. 42 (1986) 743-798] that the floor constraint induces an entropic repulsion effect which lifts the surface to an average height $H\asymp(1/β)\log L$. As an essential step in understanding the effect of entropic repulsion on the Glauber dynamics we determine the equilibrium height $H$ to within an additive constant: $H=(1/4β)\log L+O(1)$. We then show that starting from zero initial conditions the surface rises to its final height $H$ through a sequence of metastable transitions between consecutive levels. The time for a transition from height $h=aH$, $a\in(0,1)$, to height $h+1$ is roughly $\exp(cL^a)$ for some constant $c>0$. In particular, the mixing time of the dynamics is exponentially large in $L$, that is, $T_{\mathrm{MIX}}\geq e^{cL}$. We also provide the matching upper bound $T_{\mathrm{MIX}}\leq e^{c'L}$, requiring a challenging analysis of the statistics of height contours at low temperature and new coupling ideas and techniques. Finally, to emphasize the role of entropic repulsion we show that without a floor constraint at height zero the mixing time is no longer exponentially large in $L$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Harmonic pinnacles in the Discrete Gaussian model

The 2D Discrete Gaussian model gives each height function $η: \mathbb{Z}^2\to\mathbb{Z}$ a probability proportional to $\exp(-β\mathcal{H}(η))$, where $β$ is the inverse-temperature and $\mathcal{H}(η) = \sum_{x\sim y}(η_x-η_y)^2$ sums over nearest-neighbor bonds. We consider the model at large fixed $β$, where it is flat unlike its continuous analog (the Gaussian Free Field). We first establish that the maximum height in an $L\times L$ box with 0 boundary conditions concentrates on two integers $M,M+1$ with $M\sim \sqrt{(1/2πβ)\log L\log\log L}$. The key is a large deviation estimate for the height at the origin in $\mathbb{Z}^2$, dominated by "harmonic pinnacles", integer approximations of a harmonic variational problem. Second, in this model conditioned on $η\geq 0$ (a floor), the average height rises, and in fact the height of almost all sites concentrates on levels $H,H+1$ where $H\sim M/\sqrt{2}$. This in particular pins down the asymptotics, and corrects the order, in results of Bricmont, El-Mellouki and Fröhlich (1986), where it was argued that the maximum and the height of the surface above a floor are both of order $\sqrt{\log L}$. Finally, our methods extend to other classical surface models (e.g., restricted SOS), featuring connections to $p$-harmonic analysis and alternating sign matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multi-level pinning problems for random walks and self-avoiding lattice paths

We consider a generalization of the classical pinning problem for integer-valued random walks conditioned to stay non-negative. More specifically, we take pinning potentials of the form $\sum_{j\geq 0}ε_j N_j$, where $N_j$ is the number of visits to the state $j$ and $\{ε_j\}$ is a non-negative sequence. Partly motivated by similar problems for low-temperature contour models in statistical physics, we aim at finding a sharp characterization of the threshold of the wetting transition, especially in the regime where the variance $σ^2$ of the single step of the random walk is small. Our main result says that, for natural choices of the pinning sequence $\{ε_j\}$, localization (respectively delocalization) occurs if $σ^{-2}\sum_{ j\geq0}(j+1)ε_j\geqδ^{-1}$ (respectively $\le δ$), for some universal $δ<1$. Our finding is reminiscent of the classical Bargmann-Jost-Pais criteria for the absence of bound states for the radial Schrödinger equation. The core of the proof is a recursive argument to bound the free energy of the model. Our approach is rather robust, which allows us to obtain similar results in the case where the random walk trajectory is replaced by a self-avoiding path $γ$ in $\mathbb Z^2$ with weight $\exp(-β|γ|)$, $|γ|$ being the length of the path and $β>0$ a large enough parameter. This generalization is directly relevant for applications to the above mentioned contour models.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The influence of dimension on the relaxation process of East-like models

We consider the relaxation process and the out-of-equilibrium dynamics of natural generalizations to arbitrary dimensions of the well known one dimensional East process. These facilitated models are supposed to catch some of the main features of the complex dynamics of fragile glasses. We focus on the low temperature regime (small density $c \approx e^{-β}$ of the facilitating sites). In the literature the relaxation process for the above models has been assumed to be quasi-one dimensional and, in particular, their equilibration time has been computed using the relaxation time of the East model ($d=1$) on the equilibrium length scale $L_c=(1/c)^{1/d}$ in $d$-dimension. This led to the derivation of a super-Arrhenius scaling for the relaxation time of the form $T_{\rm rel} \asymp \exp(β^2/d\log 2)$. In a companion paper, using mainly renormalization group ideas and electrical networks methods, we rigorously establish that instead $T_{\rm rel} \asymp \exp(β^2/2d\log 2)$, a result showing that the relaxation process cannot be quasi-one-dimensional. The above scaling sharply confirms previous MCAMC (Monte Carlo with Absorbing Markov Chains) simulations. Next we compute the relaxation time at finite and mesoscopic length scales, and show a dramatic dependence on the boundary conditions, yet another indication of key dimensional effects. Our final result is related to the out-of-equilibrium dynamics. Starting with a single facilitating site at the origin we show that, up to length scales $L=O(L_c)$, its influence propagates much faster (on a logarithmic scale) along the diagonal direction than along the axes directions. Such unexpected result is due to a rather delicate balance between dynamical energy barriers and entropic effects in the constrained dynamics.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Mixing time bounds for oriented kinetically constrained spin models

We analyze the mixing time of a class of oriented kinetically constrained spin models (KCMs) on a d-dimensional lattice of $n^d$ sites. A typical example is the North-East model, a 0-1 spin system on the two-dimensional integer lattice that evolves according to the following rule: whenever a site's southerly and westerly nearest neighbours have spin 0, with rate one it resets its own spin by tossing a p-coin, at all other times its spin remains frozen. Such models are very popular in statistical physics because, in spite of their simplicity, they display some of the key features of the dynamics of real glasses. We prove that the mixing time is O(n log n) whenever the relaxation time is O(1). Our study was motivated by the "shape" conjecture put forward by G. Kordzakhia and S.P. Lalley.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Scaling limit and cube-root fluctuations in SOS surfaces above a wall

Consider the classical $(2+1)$-dimensional Solid-On-Solid model above a hard wall on an $L\times L$ box of $\bbZ^2$. The model describes a crystal surface by assigning a non-negative integer height $η_x$ to each site $x$ in the box and 0 heights to its boundary. The probability of a surface configuration $η$ is proportional to $\exp(-β\mathcal{H}(η))$, where $β$ is the inverse-temperature and $\mathcal{H}(η)$ sums the absolute values of height differences between neighboring sites. We give a full description of the shape of the SOS surface for low enough temperatures. First we show that with high probability the height of almost all sites is concentrated on two levels, $H(L)=\lfloor (1/4β)\log L\rfloor$ and $H(L)-1$. Moreover, for most values of $L$ the height is concentrated on the single value $H(L)$. Next, we study the ensemble of level lines corresponding to the heights $(H(L),H(L)-1,...)$. We prove that w.h.p. there is a unique macroscopic level line for each height. Furthermore, when taking a diverging sequence of system sizes $L_k$, the rescaled macroscopic level line at height $H(L_k)-n$ has a limiting shape if the fractional parts of $(1/4β)\log L_k$ converge to a noncritical value. The scaling limit is an explicit convex subset of the unit square $Q$ and its boundary has a flat component on the boundary of $Q$. Finally, the highest macroscopic level line has $L_k^{1/3+o(1)}$ fluctuations along the flat part of the boundary of its limiting shape.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Survey of Period Variations of Superhumps in SU UMa-Type Dwarf Novae. IV: The Fourth Year (2011-2012)

Continuing the project described by Kato et al. (2009, arXiv:0905.1757), we studied 86 SU UMa-type dwarf novae. We confirmed the general trends such as the relation between period derivatives and orbital periods. There are some systems showing positive period derivatives despite the long orbital periods. We observed the 2011 outburst of the WZ Sge-type dwarf nova BW Scl, and recorded an O-C diagram similar to those of previously known WZ Sge-type dwarf novae. The WZ Sge-type dwarf nova OT J184228.1+483742 showed an unusual pattern of double outbursts composed of an outburst with early superhumps and one with ordinary superhumps. We propose an interpretation that a very small growth rate of the 3:1 resonance due to an extremely low mass-ratio led to a quenching of the superoutburst before the ordinary superhumps appeared. We studied ER UMa-type dwarf novae and found that V1159 Ori showed positive superhumps similar to ER UMa in the 1990s. The recently recognized ER UMa-type object BK Lyn dominantly showed negative superhumps, and its behavior was very similar to the present-day state of ER UMa. The pattern of period variations in AM CVn-type objects were very similar to short-period hydrogen-rich SU UMa-type dwarf novae, making them helium analogue of hydrogen-rich SU UMa-type dwarf novae. SBS 1108+574, a peculiar hydrogen-rich dwarf nova below the period minimum, showed a very similar pattern of period variations to those of short-period SU UMa-type dwarf novae. The mass-ratio derived from the detected orbital period suggests that this secondary is a somewhat evolved star whose hydrogen envelope was mostly stripped during the mass-exchange. CC Scl, MASTER OT J072948.66+593824.4 and OT J173516.9+154708 showed only low-amplitude superhumps with complex profiles. These superhumps are likely a combination of closely separated two periods.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Time scale separation and dynamic heterogeneity in the low temperature East model

We consider the non-equilibrium dynamics of the East model, a linear chain of 0-1 spins evolving under a simple Glauber dynamics in the presence of a kinetic constraint which forbids flips of those spins whose left neighbor is 1. We focus on the glassy effects caused by the kinetic constraint as $q\downarrow 0$, where $q$ is the equilibrium density of the 0's. In the physical literature this limit is equivalent to the zero temperature limit. We first prove that, for any given $L=O(1/q)$, the divergence as $q\downarrow 0$ of three basic characteristic time scales of the East process of length $L$ is the same. Then we examine the problem of dynamic heterogeneity, i.e. non-trivial spatio-temporal fluctuations of the local relaxation to equilibrium, one of the central aspects of glassy dynamics. For any mesoscopic length scale $L=O(q^{-γ})$, $γ<1$, we show that the characteristic time scale of two East processes of length $L$ and $λL$ respectively are indeed separated by a factor $q^{-a}$, $a=a(γ)>0$, provided that $λ\geq 2$ is large enough (independent of $q$, $λ=2$ for $γ<1/2$). In particular, the evolution of mesoscopic domains, i.e. maximal blocks of the form $111..10$, occurs on a time scale which depends sharply on the size of the domain, a clear signature of dynamic heterogeneity. A key result for this part is a very precise computation of the relaxation time of the chain as a function of $(q,L)$, well beyond the current knowledge, which uses induction on length scales on one hand and a novel algorithmic lower bound on the other. Finally we show that no form of time scale separation occurs for $γ=1$, i.e. at the equilibrium scale $L=1/q$, contrary to what was assumed in the physical literature based on numerical simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Fredrickson-Andersen one spin facilitated model out of equilibrium

We consider the Fredrickson and Andersen one spin facilitated model (FA1f) on an infinite connected graph with polynomial growth. Each site with rate one refreshes its occupation variable to a filled or to an empty state with probability $p\in[0,1]$ or $q=1-p$ respectively, provided that at least one of its nearest neighbours is empty. We study the non-equilibrium dynamics started from an initial distribution $ν$ different from the stationary product $p$-Bernoulli measure $μ$. We assume that, under $ν$, the mean distance between two nearest empty sites is uniformly bounded. We then prove convergence to equilibrium when the vacancy density $q$ is above a proper threshold $\bar q<1$. The convergence is exponential or stretched exponential, depending on the growth of the graph. In particular it is exponential on $\bbZ^d$ for $d=1$ and stretched exponential for $d>1$. Our result can be generalized to other non cooperative models.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Metric-Aware Secure Service Orchestration

Secure orchestration is an important concern in the internet of service. Next to providing the required functionality the composite services must also provide a reasonable level of security in order to protect sensitive data. Thus, the orchestrator has a need to check whether the complex service is able to satisfy certain properties. Some properties are expressed with metrics for precise definition of requirements. Thus, the problem is to analyse the values of metrics for a complex business process. In this paper we extend our previous work on analysis of secure orchestration with quantifiable properties. We show how to define, verify and enforce quantitative security requirements in one framework with other security properties. The proposed approach should help to select the most suitable service architecture and guarantee fulfilment of the declared security requirements.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Mixing time of a kinetically constrained spin model on trees: power law scaling at criticality

On the rooted $k$-ary tree we consider a 0-1 kinetically constrained spin model in which the occupancy variable at each node is re-sampled with rate one from the Bernoulli(p) measure iff all its children are empty. For this process the following picture was conjectured to hold. As long as $p$ is below the percolation threshold $p_c=1/k$ the process is ergodic with a finite relaxation time while, for $p>p_c$, the process on the infinite tree is no longer ergodic and the relaxation time on a finite regular sub-tree becomes exponentially large in the depth of the tree. At the critical point $p=p_c$ the process on the infinite tree is still ergodic but with an infinite relaxation time. Moreover, on finite sub-trees, the relaxation time grows polynomially in the depth of the tree. The conjecture was recently proved by the second and forth author except at criticality. Here we analyse the critical and quasi-critical case and prove for the relevant time scales: (i) power law behaviour in the depth of the tree at $p=p_c$ and (ii) power law scaling in $(p_c-p)^{-1}$ when $p$ approaches $p_c$ from below. Our results, which are very close to those obtained recently for the Ising model at the spin glass critical point, represent the first rigorous analysis of a kinetically constrained model at criticality.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The East model: recent results and new progresses

The East model is a particular one dimensional interacting particle system in which certain transitions are forbidden according to some constraints depending on the configuration of the system. As such it has received particular attention in the physics literature as a special case of a more general class of systems referred to as kinetically constrained models, which play a key role in explaining some features of the dynamics of glasses. In this paper we give an extensive overview of recent rigorous results concerning the equilibrium and non-equilibrium dynamics of the East model together with some new improvements.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The shape of the $(2+1)$D SOS surface above a wall

We give a full description for the shape of the classical (2+1)\Dim Solid-On-Solid model above a wall, introduced by Temperley (1952). On an $L\times L$ box at a large inverse-temperature $β$ the height of most sites concentrates on a single level $h = \lfloor (1/4β)\log L\rfloor$ for most values of $L$. For a sequence of diverging boxes the ensemble of level lines of heights $(h,h-1,...)$ has a scaling limit in Hausdorff distance iff the fractional parts of $(1/4β)\log L$ converge to a noncritical value. The scaling limit is explicitly given by nested distinct loops formed via translates of Wulff shapes. Finally, the $h$-level lines feature $L^{1/3+o(1)}$ fluctuations from the side boundaries.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Universality in one-dimensional hierarchical coalescence processes

Motivated by several models introduced in the physics literature to study the nonequilibrium coarsening dynamics of one-dimensional systems, we consider a large class of "hierarchical coalescence processes" (HCP). An HCP consists of an infinite sequence of coalescence processes ${ξ^{(n)}(\cdot)}_{n\ge1}$: each process occurs in a different "epoch" (indexed by $n$) and evolves for an infinite time, while the evolution in subsequent epochs are linked in such a way that the initial distribution of $ξ^{(n+1)}$ coincides with the final distribution of $ξ^{(n)}$. Inside each epoch the process, described by a suitable simple point process representing the boundaries between adjacent intervals (domains), evolves as follows. Only intervals whose length belongs to a certain epoch-dependent finite range are active, that is, they can incorporate their left or right neighboring interval with quite general rates. Inactive intervals cannot incorporate their neighbors and can increase their length only if they are incorporated by active neighbors. The activity ranges are such that after a merging step the newly produced interval always becomes inactive for that epoch but active for some future epoch. Without making any mean-field assumption we show that: (i) if the initial distribution describes a renewal process, then such a property is preserved at all later times and all future epochs; (ii) the distribution of certain rescaled variables, for example, the domain length, has a well-defined and universal limiting behavior as $n\to \infty$ independent of the details of the process (merging rates, activity ranges$,...$). This last result explains the universality in the limiting behavior of several very different physical systems (e.g., the East model of glassy dynamics or the Paste-all model) which was observed in several simulations and analyzed in many physics papers. The main idea to obtain the asymptotic result is to first write down a recursive set of nonlinear identities for the Laplace transforms of the relevant quantities on different epochs and then to solve it by means of a transformation which in some sense linearizes the system.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Glauber dynamics for the quantum Ising model in a transverse field on a regular tree

Motivated by a recent use of Glauber dynamics for Monte-Carlo simulations of path integral representation of quantum spin models [Krzakala, Rosso, Semerjian, and Zamponi, Phys. Rev. B (2008)], we analyse a natural Glauber dynamics for the quantum Ising model with a transverse field on a finite graph $G$. We establish strict monotonicity properties of the equilibrium distribution and we extend (and improve) the censoring inequality of Peres and Winkler to the quantum setting. Then we consider the case when $G$ is a regular $b$-ary tree and prove the same fast mixing results established in [Martinelli, Sinclair, and Weitz, Comm. Math. Phys. (2004)] for the classical Ising model. Our main tool is an inductive relation between conditional marginals (known as the "cavity equation") together with sharp bounds on the operator norm of the derivative at the stable fixed point. It is here that the main difference between the quantum and the classical case appear, as the cavity equation is formulated here in an infinite dimensional vector space, whereas in the classical case marginals belong to a one-dimensional space.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Mixing times of monotone surfaces and SOS interfaces: a mean curvature approach

We consider stochastic spin-flip dynamics for: (i) monotone discrete surfaces in Z^3 with planar boundary height and (ii) the one-dimensional discrete Solid-on-Solid (SOS) model confined to a box. In both cases we show almost optimal bounds O(L^2polylog(L)) for the mixing time of the chain, where L is the natural size of the system. The dynamics at a macroscopic scale should be described by a deterministic mean curvature motion such that each point of the surface feels a drift which tends to minimize the local surface tension. Inspired by this heuristics, our approach consists in bounding the dynamics with an auxiliary one which, with very high probability, follows quite closely the deterministic mean curvature evolution. Key technical ingredients are monotonicity, coupling and an argument due to D.B. Wilson in the framework of lozenge tiling Markov Chains. Our approach works equally well for both models despite the fact that their equilibrium maximal height fluctuations occur on very different scales (logarithmic for monotone surfaces and L^{1/2} for the SOS model). Finally, combining techniques from kinetically constrained spin systems together with the above mixing time result, we prove an almost diffusive lower bound of order 1/L^2 up to logarithmic corrections for the spectral gap of the SOS model with horizontal size L and unbounded heights.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

"Zero" temperature stochastic 3D Ising model and dimer covering fluctuations: a first step towards interface mean curvature motion

We consider the Glauber dynamics for the Ising model with "+" boundary conditions, at zero temperature or at temperature which goes to zero with the system size (hence the quotation marks in the title). In dimension d=3 we prove that an initial domain of linear size L of "-" spins disappears within a time τ_+ which is at most L^2(\log L)^c and at least L^2/(c\log L), for some c>0. The proof of the upper bound proceeds via comparison with an auxiliary dynamics which mimics the motion by mean curvature that is expected to describe, on large time-scales, the evolution of the interface between "+" and "-" domains. The analysis of the auxiliary dynamics requires recent results on the fluctuations of the height function associated to dimer coverings of the infinite honeycomb lattice. Our result, apart from the spurious logarithmic factor, is the first rigorous confirmation of the expected behavior τ_+\simeq const\times L^2, conjectured on heuristic grounds. In dimension d=2, τ_+ can be shown to be of order L^2 without logarithmic corrections: the upper bound was proven in [Fontes, Schonmann, Sidoravicius, 2002] and here we provide the lower bound. For d=2, we also prove that the spectral gap of the generator behaves like c/L for L large, as conjectured in [Bodineau-Martinelli, 2002].

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Convergence to equilibrium of biased plane partitions

We study a single-flip dynamics for the monotone surface in (2+1) dimensions obtained from a boxed plane partition. The surface is analyzed as a system of non-intersecting simple paths. When the flips have a non-zero bias we prove that there is a positive spectral gap uniformly in the boundary conditions and in the size of the system. Under the same assumptions, for a system of size M, the mixing time is shown to be of order M up to logarithmic corrections.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Mixing Time for the Solid-on-Solid Model

We analyze the mixing time of a natural local Markov chain (the Glauber dynamics) on configurations of the solid-on-solid model of statistical physics. This model has been proposed, among other things, as an idealization of the behavior of contours in the Ising model at low temperatures. Our main result is an upper bound on the mixing time of $O~(n^{3.5})$, which is tight within a factor of $O~(sqrt{n})$. (The notation O~ hides factors that are logarithmic in n.) The proof, which in addition gives some insight into the actual evolution of the contours, requires the introduction of a number of novel analytical techniques that we conjecture will have other applications.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Polymer dynamics in the depinned phase: metastability with logarithmic barriers

We consider the stochastic evolution of a (1 + 1)-dimensional polymer in the depinned regime. At equilibrium the system exhibits a double well structure: the polymer lies(essentially) either above or below the repulsive line. As a consequence one expects a metastable behavior with rare jumps between the two phases combined with a fast thermalization inside each phase. However the energy barrier between these two phases is only logarithmic in the system size L and therefore the two relevant time scales are only polynomial in L with no clear-cut separation between them. The whole evolution is governed by a subtle competition between the diffusive behavior inside one phase and the jumps across the energy barriers. In particular the usual scenario in which the tunneling time coincides with the exponential of the energy barrier breaks down. Our main results are: (i) a proof that the mixing time of the system lies between L^{5/2} and L^{5/2+2}; (ii) the identification of two regions associated with the positive and negative phase of the polymer together with the proof of the asymptotic exponentiality of the tunneling time between them with rate equal to a half of the spectral gap.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Quasi-polynomial mixing of the 2D stochastic Ising model with "plus" boundary up to criticality

We considerably improve upon the recent result of Martinelli and Toninelli on the mixing time of Glauber dynamics for the 2D Ising model in a box of side $L$ at low temperature and with random boundary conditions whose distribution $P$ stochastically dominates the extremal plus phase. An important special case is when $P$ is concentrated on the homogeneous all-plus configuration, where the mixing time $T_{mix}$ is conjectured to be polynomial in $L$. In [MT] it was shown that for a large enough inverse-temperature $β$ and any $ε>0$ there exists $c=c(β,ε)$ such that $\lim_{L\to\infty}P(T_{mix}\geq \exp({c L^ε}))=0$. In particular, for the all-plus boundary conditions and $β$ large enough $T_{mix} \leq \exp({c L^ε})$. Here we show that the same conclusions hold for all $β$ larger than the critical value $β_c$ and with $\exp({c L^ε})$ replaced by $L^{c \log L}$ (i.e. quasi-polynomial mixing). The key point is a modification of the inductive scheme of [MT] together with refined equilibrium estimates that hold up to criticality, obtained via duality and random-line representation tools for the Ising model. In particular, we establish new precise bounds on the law of Peierls contours which quantitatively sharpen the Brownian bridge picture established e.g. in [Greenberg-Ioffe (2005)],[Higuchi (1979)],[Hryniv (1998)].

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The multi-state hard core model on a regular tree

The classical hard core model from statistical physics, with activity $λ> 0$ and capacity $C=1$, on a graph $G$, concerns a probability measure on the set ${\mathcal I}(G)$ of independent sets of $G$, with the measure of each independent set $I \in {\mathcal I}(G)$ being proportional to $λ^{|I|}$. Ramanan et al. proposed a generalization of the hard core model as an idealized model of multicasting in communication networks. In this generalization, the {\em multi-state} hard core model, the capacity $C$ is allowed to be a positive integer, and a configuration in the model is an assignment of states from $\{0,\ldots,C\}$ to $V(G)$ (the set of nodes of $G$) subject to the constraint that the states of adjacent nodes may not sum to more than $C$. The activity associated to state $i$ is $λ^{i}$, so that the probability of a configuration $σ:V(G)\rightarrow \{0,\ldots, C\}$ is proportional to $λ^{\sum_{v \in V(G)} σ(v)}$. In this work, we consider this generalization when $G$ is an infinite rooted $b$-ary tree and prove rigorously some of the conjectures made by Ramanan et al. In particular, we show that the $C=2$ model exhibits a (first-order) phase transition at a larger value of $λ$ than the $C=1$ model exhibits its (second-order) phase transition. In addition, for large $b$ we identify a short interval of values for $λ$ above which the model exhibits phase co-existence and below which there is phase uniqueness. For odd $C$, this transition occurs in the region of $λ= (e/b)^{1/\ceil{C/2}}$, while for even $C$, it occurs around $λ=(\log b/b(C+2))^{2/(C+2)}$. In the latter case, the transition is first-order.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Facilitated oriented spin models:some non equilibrium results

We analyze the relaxation to equilibrium for kinetically constrained spin models (KCSM) when the initial distribution $ν$ is different from the reversible one, $μ$. This setting has been intensively studied in the physics literature to analyze the slow dynamics which follows a sudden quench from the liquid to the glass phase. We concentrate on two basic oriented KCSM: the East model on $\bbZ$, for which the constraint requires that the East neighbor of the to-be-update vertex is vacant and the model on the binary tree introduced in \cite{Aldous:2002p1074}, for which the constraint requires the two children to be vacant. While the former model is ergodic at any $p\neq 1$, the latter displays an ergodicity breaking transition at $p_c=1/2$. For the East we prove exponential convergence to equilibrium with rate depending on the spectral gap if $ν$ is concentrated on any configuration which does not contain a forever blocked site or if $ν$ is a Bernoulli($p'$) product measure for any $p'\neq 1$. For the model on the binary tree we prove similar results in the regime $p,p'<p_c$ and under the (plausible) assumption that the spectral gap is positive for $p<p_c$. By constructing a proper test function we also prove that if $p'>p_c$ and $p\leq p_c$ convergence to equilibrium cannot occur for all local functions. Finally we present a very simple argument (different from the one in \cite{Aldous:2002p1074}) based on a combination of combinatorial results and ``energy barrier'' considerations, which yields the sharp upper bound for the spectral gap of East when $p\uparrow 1$.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Facilitated spin models: recent and new results

Facilitated or kinetically constrained spin models (KCSM) are a class of interacting particle systems reversible w.r.t. to a simple product measure. Each dynamical variable (spin) is re-sampled from its equilibrium distribution only if the surrounding configuration fulfills a simple local constraint which \emph{does not involve} the chosen variable itself. Such simple models are quite popular in the glass community since they display some of the peculiar features of glassy dynamics, in particular they can undergo a dynamical arrest reminiscent of the liquid/glass transitiom. Due to the fact that the jumps rates of the Markov process can be zero, the whole analysis of the long time behavior becomes quite delicate and, until recently, KCSM have escaped a rigorous analysis with the notable exception of the East model. In these notes we will mainly review several recent mathematical results which, besides being applicable to a wide class of KCSM, have contributed to settle some debated questions arising in numerical simulations made by physicists. We will also provide some interesting new extensions. In particular we will show how to deal with interacting models reversible w.r.t. to a high temperature Gibbs measure and we will provide a detailed analysis of the so called one spin facilitated model on a general connected graph.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Relaxation times of kinetically constrained spin models with glassy dynamics

We analyze the density and size dependence of the relaxation time $τ$ for kinetically constrained spin systems. These have been proposed as models for strong or fragile glasses and for systems undergoing jamming transitions. For the one (FA1f) or two (FA2f) spin facilitated Fredrickson-Andersen model at any density $ρ<1$ and for the Knight model below the critical density at which the glass transition occurs, we show that the persistence and the spin-spin time auto-correlation functions decay exponentially. This excludes the stretched exponential relaxation which was derived by numerical simulations. For FA2f in $d\geq 2$, we also prove a super-Arrhenius scaling of the form $\exp(1/(1-ρ))\leq τ\leq\exp(1/(1-ρ)^2)$. For FA1f in $d$=$1,2$ we rigorously prove the power law scalings recently derived in \cite{JMS} while in $d\geq 3$ we obtain upper and lower bounds consistent with findings therein. Our results are based on a novel multi-scale approach which allows to analyze $τ$ in presence of kinetic constraints and to connect time-scales and dynamical heterogeneities. The techniques are flexible enough to allow a variety of constraints and can also be applied to conservative stochastic lattice gases in presence of kinetic constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Phase ordering after a deep quench: the stochastic Ising and hard core gas models on a tree

Consider a low temperature stochastic Ising model in the phase coexistence regime with Markov semigroup $P_t$. A fundamental and still largely open problem is the understanding of the long time behavior of $\d_\h P_t$ when the initial configuration $\h$ is sampled from a highly disordered state $ν$ (e.g. a product Bernoulli measure or a high temperature Gibbs measure). Exploiting recent progresses in the analysis of the mixing time of Monte Carlo Markov chains for discrete spin models on a regular $b$-ary tree $\Tree^b$, we tackle the above problem for the Ising and hard core gas (independent sets) models on $\Tree^b$. If $ν$ is a biased product Bernoulli law then, under various assumptions on the bias and on the thermodynamic parameters, we prove $ν$-almost sure weak convergence of $\d_\h P_t$ to an extremal Gibbs measure (pure phase) and show that the limit is approached at least as fast as a stretched exponential of the time $t$. In the context of randomized algorithms and if one considers the Glauber dynamics on a large, finite tree, our results prove fast local relaxation to equilibrium on time scales much smaller than the true mixing time, provided that the starting point of the chain is not taken as the worst one but it is rather sampled from a suitable distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

Relaxation time of anisotropic simple exclusion processes and quantum Heisenberg models

Motivated by an exact mapping between anisotropic half integer spin quantum Heisenberg models and asymmetric diffusions on the lattice, we consider an anisotropic simple exclusion process with $N$ particles in a rectangle of $\bbZ^2$. Every particle at row $h$ tries to jump to an arbitrary empty site at row $h\pm 1$ with rate $q^{\pm 1}$, where $q\in (0,1)$ is a measure of the drift driving the particles towards the bottom of the rectangle. We prove that the spectral gap of the generator is uniformly positive in $N$ and in the size of the rectangle. The proof is inspired by a recent interesting technique envisaged by E. Carlen, M.C. Carvalho and M. Loss to analyze the Kac model for the non linear Boltzmann equation. We then apply the result to prove precise upper and lower bounds on the energy gap for the spin--S, ${\rm S}\in \frac12\bbN$, XXZ chain and for the 111 interface of the spin--S XXZ Heisenberg model, thus generalizing previous results valid only for spin $\frac12$.

0 citations0 reviewsNo code linkedOpen access
preprint2001arXiv

Asymmetric diffusion and the energy gap above the 111 ground state of the quantum XXZ model

We consider the anisotropic three dimensional XXZ Heisenberg ferromagnet in a cylinder with axis along the 111 direction and boundary conditions that induce ground states describing an interface orthogonal to the cylinder axis. Let $L$ be the linear size of the basis of the cylinder. Because of the breaking of the continuous symmetry around the $\hat z$ axis, the Goldstone theorem implies that the spectral gap above such ground states must tend to zero as $L\to \infty$. In \cite{BCNS} it was proved that, by perturbing in a sub--cylinder with basis of linear size $R\ll L$ the interface ground state, it is possible to construct excited states whose energy gap shrinks as $R^{-2}$. Here we prove that, uniformly in the height of the cylinder and in the location of the interface, the energy gap above the interface ground state is bounded from below by $\text{const.}L^{-2}$. We prove the result by first mapping the problem into an asymmetric simple exclusion process on $\Z^3$ and then by adapting to the latter the recursive analysis to estimate from below the spectral gap of the associated Markov generator developed in \cite{CancMart}. Along the way we improve some bounds on the equivalence of ensembles already discussed in \cite{BCNS} and we establish an upper bound on the density of states close to the bottom of the spectrum.

0 citations0 reviewsNo code linkedOpen access