Titles & Questions

We discuss the setting of spin systems which exhibit weak spatial mixing but not strong spatial mixing. We seek to understand ‘bad’ partial configurations which cause long-range correlation.

In this work, we establish novel, optimum mixing results  for the Glauber dynamics on the Hard-core and Ising models using the powerful Spectral Independence method from [Anari, Liu, Oveis-Gharan: FOCS 2020].   The  mixing bounds are expressed in terms of matrix norms of the underlying graph G rather than the maximum degree Δ. We obtain one set of results with the mixing bounds expressed in terms of ||A||_2, where A is the adjacency matrix. These results improve on the seminal work in [Hayes: FOCS 2006].

In a second set of results, we obtain, for the first time, mixing bounds that are expressed in terms of ||H^N||^(1/N)_2 where H is the Hashimoto non-backtracking matrix, while we can choose N to be any bounded integer. Even though the results with the non-backtracking matrix are interesting in their own right, they have some interesting consequences:

(a) they include the max degree mixing bounds as a special case,

(b) they allow us to refine the celebrated connection between the hardness of approximate counting and the phase transitions from statistical physics,

(c) for locally tree-like graphs, they imply rapid mixing bounds expressed in terms of the local connective constant.

We obtain all the above by proposing a novel analysis to bound the maximum eigenvalue of I^(Λ,τ), which yields more accurate estimations than earlier works.

On the Burnside process

In the evolving sorting problem, introduced by Anagnostopoulos, Kumar, Mahdian and Upfal (2011), the true total order changes while the sorting algorithm is processing the input. More precisely, each comparison operation of the sorting algorithm is followed by a sequence of evolution steps, where an evolution step perturbs the rank of a random item by a small random value. The goal is to maintain an ordering that remains close to the true order over time. In this talk, I will present an analysis of a very simple sorting algorithm, which samples a random pair of adjacent items in each step and swaps them if they are out of order. We show that the algorithm  achieves and maintains, with high probability, optimal total deviation and optimal maximum deviation, under very general model settings. 

Reference: arXiv:2404.08162

The facilitated exclusion process (FEP) is a particle system, where particles evolve on a discrete lattice, making random jumps while obeying local constraints. Because of these constraints, it is nonreversible, and has transient configurations: after a finite time, it is no longer transient and is either frozen or reaches an ergodic component. We estimated the transience time, using a mapping to another process, the SSEP with traps. When the FEP doesn’t freeze and continues moving, one can study its mixing time. It is not hard to show cutoff for the SSEP with traps’ mixing time, by showing the time spent in the transient phase and the ergodic phase balance each other out. The same kind of result can be obtained for the FEP, but with a more involved mapping. 

In both cases, the transience time is a key ingredient. It is natural to ask what is the worst initial configuration for the transience time. However, the lack of monotonicity in the FEP makes this question quite difficult to answer. 

In this talk, we discuss recent progress for mixing times of the simple exclusion process with open boundaries. We give an overview on the available techniques and results for the open ASEP. Moreover, we discuss the question of mixing times for projections of the exclusion process to subintervals. 

The Glauber-Exclusion process, an interacting particle system introduced by De Masi, Ferrari, and Lebowitz, is a superposition of a Glauber dynamics and the symmetric simple exclusion process (SSEP) on a lattice. It was shown to admit a reaction-diffusion equation as the hydrodynamic limit. In this talk, we introduce the information percolation framework invented by Lubetzky and Sly and explain how it can be used to study the mixing times of our process. After defining a notion of temperature regimes via the equation in the hydrodynamic limit, we prove cutoff for the attractive model in the high-temperature regime, analogous to the results of Lubetzky and Sly for the Glauber dynamics of the Ising model. Our results show a connection between the hydrodynamic limit and the mixing behavior of the large but finite system. Finally, we describe our attempt to use this method to study other models.