About

Alistair Sinclair is a professor in the Department of Statistics at the University of California, Berkeley. His research interests include algorithms, applied probability, random walks, Markov chains, computational applications of randomness, Markov chain Monte Carlo, statistical physics, and combinatorial optimization. Most of his work involves applying probabilistic ideas to design or analyze algorithms, with a focus on theoretical computer science, randomized computation, phase transitions, and nonlinear dynamical systems.

Research topics

• Mathematics
• Combinatorics
• Discrete mathematics
• Computer science
• Statistical physics

Selected publications

• Diversity in Evolutionary Dynamics (Supporting Information)

  Figshare · 2026-03-21

  articleOpen accessSenior author

  Proofs of mathematical statements

  PublisherDOI

• Diversity in Evolutionary Dynamics (Supporting Information)

  Figshare · 2026-03-21

  articleOpen accessSenior author

  Proofs of mathematical statements

  PublisherDOI

• Diversity in evolutionary dynamics

  Journal of The Royal Society Interface · 2026-04-29

  preprintOpen accessSenior author

  We consider the dynamics imposed by natural selection on the populations of two competing, sexually reproducing, haploid species. In this setting, the fitness of any genotype varies over time due to the changing population mix of the competing species; crucially, unlike other approaches to ensuring time-varying fitnesses, in our model, this fitness variation arises intrinsically from fixed-fitness interactions between the species themselves. Previous work on this model showed that, in the special case where each of the two species exhibits just two phenotypes, genetic diversity is maintained at all times. This finding supported the tenet that sexual reproduction is advantageous because it promotes diversity, which increases the survivability of a species. In the present article, we consider the more realistic case where there are more than two phenotypes available to each species. The conclusions about diversity in general turn out to be very different from the two-phenotype case. Our first result is negative: namely, we show that sexual reproduction does not guarantee the maintenance of diversity at all times, i.e. the above two-phenotype result does not generalize. Our counterexample consists of two competing species with just three phenotypes each. We show that, for any time t0 and any ε > 0, there is a time t ≥ t0 at which the combined diversity of both species is smaller than ε. Our main result is a complementary positive statement, which says that in any non-degenerate system, diversity is maintained in a weaker, 'infinitely often' sense. Here, non-degeneracy is the condition that the game possesses no strict pure Nash equilibria. Thus, our results refute the supposition that sexual reproduction ensures diversity at all times, but affirm a weaker assertion that extended periods of high diversity are necessarily a recurrent event.

  PublisherDOI

• Diversity in Evolutionary Dynamics (Supporting Information)

  Figshare · 2026-03-21

  articleOpen accessSenior author

  Proofs of mathematical statements

  PublisherDOI

• Supplementary material from "Diversity in Evolutionary Dynamics"

  Figshare · 2026-03-21

  otherOpen accessSenior author

  We consider the dynamics imposed by natural selection on the populations of two competing, sexually reproducing, haploid species. In this setting, the fitness of any genotype varies intrinsically over time due to the changing population mix of the competing species. Previous work on this model showed that, in the special case where each of the two species exhibits just two phenotypes, genetic diversity is maintained at all times. This finding supported the tenet that sexual reproduction is advantageous because it promotes diversity, which increases the survivability of a species. In the present paper we consider the more realistic case where there are more than two phenotypes available to each species, obtaining strikingly different results: 1. There exist systems (in which both species have three or more phenotypes) for which the combined diversity of both species becomes arbitrarily small at arbitrarily large times. 2. In contrast, in <i>every</i> non-degenerate system, diversity <i>is</i> maintained in a weaker, “infinitely often” sense. (This is our main result.) Thus, our results refute the supposition that sexual reproduction ensures diversity at <i>all</i> times, but affirm a weaker assertion that extended periods of high diversity necessarily recur infinitely often.

  PublisherDOI

• On quantum to classical comparison for Davies generators

  ArXiv.org · 2025-10-08

  preprintOpen access

  Despite extensive study, our understanding of quantum Markov chains remains far less complete than that of their classical counterparts. [Temme'13] observed that the Davies Lindbladian, a well-studied model of quantum Markov dynamics, contains an embedded classical Markov generator, raising the natural question of how the convergence properties of the quantum and classical dynamics are related. While [Temme'13] showed that the spectral gap of the Davies Lindbladian can be much smaller than that of the embedded classical generator for certain highly structured Hamiltonians, we show that if the spectrum of the Hamiltonian does not contain long arithmetic progressions, then the two spectral gaps must be comparable. As a consequence, we prove that for a large class of Hamiltonians, including those obtained by perturbing a fixed Hamiltonian with a generic external field, the quantum spectral gap remains within a constant factor of the classical spectral gap. Our result aligns with physical intuition and enables the application of classical Markov chain techniques to the quantum setting. The proof is based on showing that any ``off-diagonal'' eigenvector of the Davies generator can be used to construct an observable which commutes with the Hamiltonian and has a Lindbladian Rayleigh quotient which can be upper bounded in terms of that of the original eigenvector's Lindbladian Rayleigh quotient. Thus, a spectral gap for such observables implies a spectral gap for the full Davies generator.

  PublisherOA PDFDOI

• Nonlinear Dynamics for the Ising Model

  Communications in Mathematical Physics · 2024-10-12 · 1 citations

  articleOpen accessSenior author

  Abstract We introduce and analyze a natural class of nonlinear dynamics for spin systems such as the Ising model. This class of dynamics is based on the framework of mass action kinetics, which models the evolution of systems of entities under pairwise interactions, and captures a number of important nonlinear models from various fields, including chemical reaction networks, Boltzmann’s model of an ideal gas, recombination in population genetics and genetic algorithms. In the context of spin systems, it is a natural generalization of linear dynamics based on Markov chains, such as Glauber dynamics and block dynamics, which are by now well understood. However, the inherent nonlinearity makes the dynamics much harder to analyze, and rigorous quantitative results so far are limited to processes which converge to essentially trivial stationary distributions that are product measures. In this paper we provide the first quantitative convergence analysis for natural nonlinear dynamics in a combinatorial setting where the stationary distribution contains non-trivial correlations, namely spin systems at high temperatures. We prove that nonlinear versions of both the Glauber dynamics and the block dynamics converge to the Gibbs distribution of the Ising model (with given external fields) in times $$O(n\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $$O(\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> respectively, where n is the size of the underlying graph (number of spins). Given the lack of general analytical methods for such nonlinear systems, our analysis is unconventional, and combines tools such as information percolation (due in the linear setting to Lubetzky and Sly), a novel coupling of the Ising model with Erdős-Rényi random graphs, and non-traditional branching processes augmented by a “fragmentation” process. Our results extend immediately to any spin system with a finite number of spins and bounded interactions.

  PublisherOA PDFDOI

• Nonlinear Dynamics for the Ising Model

  2024-06-10 · 1 citations

  articleOpen accessSenior author

  We introduce and analyze a natural class of nonlinear dynamics for spin systems such as the Ising model. This class of dynamics is based on the framework of mass action kinetics, which models the evolution of systems of entities under pairwise interactions, and captures a number of important nonlinear models from various fields, including chemical reaction networks, Boltzmann’s model of an ideal gas, recombination in population genetics, and genetic algorithms. In the context of spin systems, it is a natural generalization of linear dynamics based on Markov chains, such as Glauber dynamics and block dynamics, which are by now well understood. However, the inherent nonlinearity makes the dynamics much harder to analyze, and rigorous quantitative results so far are limited to processes which converge to essentially trivial stationary distributions that are product measures. In this paper we provide the first quantitative convergence analysis for natural nonlinear dynamics in a combinatorial setting where the stationary distribution contains non-trivial correlations, namely spin systems at high temperatures. We prove that nonlinear versions of both the Glauber dynamics and the block dynamics converge to the Gibbs distribution of the Ising model (with given external fields) in times O(nlogn) and O(logn) respectively, where n is the size of the underlying graph (number of spins). Given the lack of general analytical methods for such nonlinear systems, our analysis is unconventional, and combines tools such as information percolation (due in the linear setting to Lubetzky and Sly), a novel coupling of the Ising model with Erdős-Rényi random graphs, and non-traditional branching processes augmented by a ”fragmentation” process. Our results extend immediately to any spin system with a finite number of spins and bounded interactions.

  PublisherOA PDFDOI

• Spatial mixing and the random-cluster dynamics on lattices

  Society for Industrial and Applied Mathematics eBooks · 2023-01-01 · 4 citations

  book-chapterSenior author

  An important paradigm in the understanding of mixing times of Glauber dynamics for spin systems is the correspondence between spatial mixing properties of the models and bounds on the mixing time of the dynamics. This includes, in particular, the classical notions of weak and strong spatial mixing, which have been used to show the best known mixing time bounds in the high-temperature regime for the Glauber dynamics for the Ising and Potts models. Glauber dynamics for the random-cluster model does not naturally fit into this spin systems framework because its transition rules are not local. In this paper, we present various implications between weak spatial mixing, strong spatial mixing, and the newer notion of spatial mixing within a phase, and mixing time bounds for the random-cluster dynamics in finite subsets of ℤd for general d  2. These imply a host of new results, including optimal O(N log N) mixing for the random cluster dynamics on torii and boxes on N vertices in ℤd at all high temperatures and at sufficiently low temperatures, and for large values of q quasi-polynomial (or quasi-linear when d = 2) mixing time bounds from random phase initializations on torii at the critical point (where by contrast the mixing time from worst-case initializations is exponentially large). In the same parameter regimes, these results translate to fast sampling algorithms for the Potts model on ℤd for general d. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.11195

  PublisherDOI

• Low-temperature Ising dynamics with random initializations

  The Annals of Applied Probability · 2023-10-01

  articleSenior author

  It is well known that Glauber dynamics on spin systems typically suffer exponential slowdowns at low temperatures. This is due to the emergence of multiple metastable phases in the state space, separated by narrow bottlenecks that are hard for the dynamics to cross. It is a folklore belief that if the dynamics is initialized from an appropriate random mixture of ground states, one for each phase, then convergence to the Gibbs distribution should be much faster. However, such phenomena have largely evaded rigorous analysis, as most tools in the study of Markov chain mixing times are tailored to worst-case initializations. In this paper we develop a general framework towards establishing this conjectured behavior for the Ising model. In the classical setting of the Ising model on an N-vertex torus in Zd, our framework implies that the mixing time for the Glauber dynamics, initialized from a 12-12 mixture of the all-plus and all-minus configurations, is N1+o(1) in dimension d=2, and at most quasi-polynomial in all dimensions d≥3, at all temperatures below the critical one. The key innovation in our analysis is the introduction of the notion of “weak spatial mixing within a phase”, a low-temperature adaptation of the classical concept of weak spatial mixing. We show both that this new notion is strong enough to control the mixing time from the above random initialization (by relating it to the mixing time with plus boundary condition at O(logN) scales), and that it holds at all low temperatures in all dimensions. This framework naturally extends to more general families of graphs. To illustrate this, we use the same approach to establish optimal O(NlogN) mixing for the Ising Glauber dynamics on random regular graphs at sufficiently low temperatures, when initialized from the same random mixture.

  PublisherDOI

Recent grants

• AF: Small: Random Processes, Statistical Physics and Computation

  NSF · $450k · 2014–2018

• AF: Small: Approximate Counting, Stochastic Local Search and Nonlinear Dynamics

  NSF · $500k · 2018–2023

• AF: Medium: Collaborative Research: Information Compression in Algorithm Design and Statistical Physics

  NSF · $286k · 2015–2019

• ITR/SY: Discrete Models & Algorithms in the Sciences

  NSF · $2.9M · 2001–2007

• AF: Small: Markov Chains, Statistical Physics, and Mobile Geometric Graphs

  NSF · $498k · 2010–2014

Frequent coauthors

• Piyush Srivastava

  Tata Institute of Fundamental Research

  48 shared

• Claire Kenyon

  33 shared

• Dorit S. Hochbaum

  University of California, Berkeley

  27 shared

• Bruno Petazzoni

  Laboratoire de l'Informatique du Parallélisme

  25 shared

• Maxime Crochemore

  Centre National de la Recherche Scientifique

  25 shared

• Mike Grigoriadis

  Laboratoire de l'Informatique du Parallélisme

  25 shared

• Uriel Feige

  25 shared

• Nicolas Puech

  Télécom Paris

  25 shared