Titles and Abstracts

We present a local algorithm for computing a near maximum cut or a near minimum bisection of a regular graph of large girth and large degree. When given a k-regular graph of girth 2L, the algorithm produces a cut with the following two extremal properties when k and L are large:

(1) The achieved cut value is approximately optimal among all L-local algorithms. 

(2) This value approximately matches the true cut value on random k-regular graphs.           

As a consequence, random regular graphs have approximately minimum max-cut value, and maximum min-bisection value among all locally-treelike regular graphs of the same degree. This can be seen as a combinatorial version of the near-Ramanujan property of random regular graphs. 

----------------------------

Her are some useful references as background for the talk:

• Lyons. Factors of IID on trees.  https://arxiv.org/abs/1401.4197

• Dembo, Montanari, Sen. Extremal cuts of sparse random graphs. https://arxiv.org/abs/1503.03923

• El Alaoui, Montanari, Sellke. Local algorithms for Maximum cut and minimum bisection of locally tree-like graphs of large degree. https://arxiv.org/abs/2111.06813

In this talk we consider the well-known Markov chain called Glauber Dynamics. This is used extensively for approximate sampling from Gibbs distributions such as the well-known Ising model, or its generalisation the Potts model, the Hard-core model of lattice gasses and many other distributions.  In this setting, the corresponding Gibbs distribution is the limit -equilibrium- distribution of Glauber dynamics.

Our focus will be on the mixing time of Glauber dynamics. Specifically, we consider connections between the mixing time of Glauber dynamics and the  Strong Spatial Mixing (SSM) of the underlying Gibbs distribution. We are focusing on SSM for Gibbs distributions on trees, which expresses (in a strong sense) an asymptotic independence between the configuration at the root and that of vertices away from the root.

We discuss how,  for 2-spin Gibbs distributions, SSM on the tree of maximum degree \Delta, implies SSM on any graph G of maximum degree \Delta. Furthermore,  we present recent results which demonstrate that the on-set of SSM implies rapid mixing of the Glauber dynamics. That is O(n\log n) mixing time, where n is the size of the system.

Specifically, we discuss Weitz's construction of the Tree of Self-avoiding Walks which implies that the worst-case graph to study SSM is the tree. Furthermore, we discuss the Spectral Independence method which -using the theory of high-dimensional expanders- establishes a connection between SSM of Gibbs distribution and rapid mixing of Glauber dynamics.

References:

Dror Weitz: Counting independent sets up to the tree threshold. STOC 2006: 140-149

Nima Anari, Kuikui Liu, Shayan Oveis Gharan: Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model.  CoRR abs/2001.00303 (2020)

Zongchen Chen, Kuikui Liu, Eric Vigoda: Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. CoRR abs/2004.09083 (2020)

Further reading:

Zongchen Chen, Kuikui Liu, Eric Vigoda: Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion. CoRR abs/2011.02075 (2020)

Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang: Optimal mixing for two-state anti-ferromagnetic spin systems. FOCS 2022: 588-599

Liang Li, Pinyan Lu, Yitong Yin: Correlation Decay up to Uniqueness in Spin Systems. CoRR abs/1111.7064 (2011)

We present novel results for fast mixing of Glauber dynamics using the newly introduced and powerful Spectral Independence method from [Anari, Liu, Oveis-Gharan: FOCS 2020].

In our results, the parameters of the Gibbs distribution are expressed in terms of the spectral radius of the adjacency matrix of G, or that of the Hashimoto non-backtracking matrix.  The analysis relies on new techniques that we introduce to bound the maximum eigenvalue of the pairwise influence matrix I_G for the two spin Gibbs distribution \mu.

There is a common framework that underlies these techniques which we call the topological method. The idea is to systematically exploit the well-known connections between I_G and the topological construction called Tree of Self-avoiding walks. Our approach is novel and gives new insights to the problem of establishing spectral independence for Gibbs distributions. More importantly, it allows us to derive new -- improved -- rapid mixing bounds for Glauber dynamics on distributions such as the Hard-core model and the Ising model for graphs that the spectral radius is smaller than the maximum degree.

Reference:

Charilaos Efthymiou: Spectral Independence Beyond Uniqueness using the topological method. https://arxiv.org/abs/2211.03753

These talks will be a self-contained introduction to expanders

and relative expanders, focusing on the case of d-regular graphs on n

vertices with d fixed and n large.  The first talk will be introductory,

including (1) definition and motivation of the spectral definition of

expanders, (2) some known results, (3) covering maps (lifts) and

relative expansion.  The second talk will discuss aspects of covering

theory and group theory, and discuss some current topics of research.

• The overlap gap property: A topological barrier to optimizing over random structures: https://www.pnas.org/doi/abs/10.1073/pnas.2108492118

• LIMITS OF LOCAL ALGORITHMS OVER SPARSE RANDOM GRAPHS: https://www.jstor.org/stable/26362256

• On the solution-space geometry of random constraint satisfaction problems: https://dl.acm.org/doi/abs/10.1145/1132516.1132537?casa_token=VoJ4QxN0LN0AAAAA:p2n-HKbiiwDBp09ngIp6Kb-Ng8rPHcoTjyi3wrMHgB1vbiTINFHxlAL39OnNujKJF4Aj9WYExN0

• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics: https://arxiv.org/abs/2004.12063 

• Optimal low-degree hardness of maximum independent set: https://ems.press/journals/msl/articles/4180358

• Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses: https://ieeexplore.ieee.org/abstract/document/9996802?casa_token=XxqB853ne98AAAAA:yvoKI2S_4705qpKvmqNvzpLuaRTFulq0-0jIQb6K_pXRVRQUAcrMC7gk7dilzcVZDozzMMM

I will discuss uniqueness and non-uniqueness for percolation on groups. The first talk will be an introduction discussing some classical results, while the second will cover more recent developments. 

For those who wish to read ahead: The lecture notes from my 2021 ICTS mini-course cover some of the same material http://www.its.caltech.edu/~thutch/ICTS_March_2021.pdf

The K_4^3 bootstrap percolation process is defined as follows: start with an initial set of ``infected'' triangles Y, where each of the {n \choose 3} triangles with vertices [n]={1,2,…,n} appears independently with probability p; then repeatedly add to it a new triangle {a,b,c} if there exists a tetrahedron in which this is the only missing face,(i.e., if for some x the 3 triangles {a,b,x},{a,x,c},{x,b,c} are already infected). Let Y_\infty denoted the final state of the process. What is the critical probability p(n) so that Y_\infty would typically contain a specific triangle {1,2,3}? How many triangles would Y_\infty typically have below that threshold? When would Y_\infty typically contain all triangles? 

Equivalently, a stacked triangulation of a triangle with labels in [n], a.k.a. an Appolonian Network, is one obtained by repeatedly subdividing a triangle {a,b,c} into 3 new triangles {a,b,x},{a,x,c},{x,b,c} via a label x in [n]. The above questions would amount to asking, e.g., about the critical probability so that the random simplicial complex Y_2(n,p) would typically contain the faces of a stacked triangulation of every triangle {a,b,c}.

We consider these questions for a general dimension d \geq 2, and our results identify the critical threshold p_c for stacked triangulations: we show that p_c is asymptotically (C(d) n)^(-1/d), where the constant C(d) is the growth rate of the Fuss--Catalan numbers of order d. The proof hinges on a second moment argument in the supercritical regime, and on Kalai's algebraic shifting in the subcritical regime.

Joint work with Yuval Peled.

The interface between the plus and minus phases in the low temperature 3D Ising model has been intensely studied since Dobrushin’s pioneering works in the early 1970’s established its rigidity. Advances in the last five years yielded the tightness of the maximum of this interface, in a cylinder of side length n, around a mean that is asymptotically c log(n) for an explicit c (depending on the temperature). In this talk we will present new analogous results for the 3D Potts models. Compared to 3D Ising, the Potts model and its lack of monotonicity form obstacles for existing methods, calling for new proof ideas, while its interfaces (and associated extrema) exhibit richer behavior.

Joint work with Joseph Chen. 

Given a discrete set of points in a metric space, called nuclei, one associates to each such nucleus its Voronoi cell, which consists of all points closer to it than to other nuclei. This construction is widely used in mathematics, science, and engineering; it is even used in baking. In Euclidean space, one commonly uses a homogeneous Poisson point process to assign the locations of the nuclei. As the intensity of the point process tends to 0, the nuclei spread out and disappear in the limit, with each pair of points eventually belonging to the same cell. Surprisingly, this does not happen in other settings such as hyperbolic space; instead, one obtains a Voronoi tessellation without nuclei! We describe properties of such a limiting tessellation, as well as analogous behavior on Cayley graphs of finitely generated groups. We will illustrate results with many pictures and several animations. The talk is based on work of Sandeep Bhupatiraju and joint work in progress with Matteo d'Achille, Nicolas Curien, Nathanael Enriquez, and Meltem Unel. We will not assume knowledge of Poisson point processes or of hyperbolic space.

Jewel in the 3D Ideal Poisson-Voronoi tessellation:

https://sketchfab.com/3d-models/jewel-77038e94cc5f4053a0d62f2d50316256

Foam in the 3D Ideal Poisson-Voronoi tessellation:

https://sketchfab.com/3d-models/foam-d5a6b8aac322480eb8ead3efe18d9e74

References (none are necessary to understand the talk):

• Sandeep Bhupatiraju, The low-intensity limit of Bernoulli-Voronoi and Poisson-Voronoi measures

• Ideal Poisson-Voronoi tessellations on hyperbolic spaces, I https://arxiv.org/abs/2303.16831

• John G. Ratcliffe. Foundations of Hyperbolic Manifolds, volume 149 of Graduate Texts in Mathematics. Springer, New York, second edition, 2006

• Jesper Møller. Lectures on Random Voronoi Tessellations. Springer New York, New York, NY, 1994

Variable-speed, continuous-time random walk on a graph is given by an assignment of nonnegative rates to its edges.  There are independent Poisson processes associated to the edges with the given rates. When a walker is at a vertex, it jumps to a neighbor at the time of the next event that occurs for the corresponding incident edges. In the case of a Cayley graph of a finitely generated group, we are particularly interested in the setting where the edge rates depend only on the corresponding generators.  Our lecture is concerned with monotonicity in the rates for various fundamental properties of random walks.  We will survey results, counterexamples, and open questions. We will give general ideas of proofs, but avoid technicalities. Nonamenable groups are the interesting ones for many of the questions we discuss.

References (none are necessary to understand the talk):

• Monotonicity for continuous-time random walks, Ann. Probab 51, no. 3 (2023), 1112--1138 https://rdlyons.pages.iu.edu/#major

• Björner, A. and Brenti, F. (2005). Combinatorics of Coxeter Groups. Graduate Texts in Mathematics 231. Springer, New York. MR2133266

• http://geometricolor.ch/images/geometricolor/sphericalKaleidoscopeApp.html

• Lyons, R. (2018). Monotonicity of average return probabilities for random walks in random environments.  In Unimodularity in Randomly Generated Graphs. Contemp. Math. 719 1â??9. Amer. Math. Soc., Providence, RI. MR3880007 https://doi.org/10.1090/conm/719/14464  https://rdlyons.pages.iu.edu/#avgrtn

• Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Probab. 12 1454â??1508. MR2354165 https://doi.org/10.1214/EJP.v12-463 https://rdlyons.pages.iu.edu/#urn

• Markov Chains and Mixing Times, second edition. David A. Levin and Yuval Peres  https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf

The hard sphere gas is an easy-to-describe model of particles interacting in the continuum.  Consider a box U in Euclidean space (or another reasonably nice space, like a Riemannian manifold) and place down a Poisson process in U conditioned on no points being within distance r of each other.  As the intensity of the process varies, what can be said about this model?   Despite the simplicity of the description and a century of work on this model, many of the most fundamental problems remain wide open.  We'll discuss the state of the art on the hard sphere gas, comparisons to other models such as the hard-core model, and describe how tools from combinatorics and theoretical computer science can be used to analyze this model.  Portions of this talk will be based on joint work with Will Perkins.

References: "Analyticity for Classical Gasses via Recursion." Michelen and Perkins. Communications in Mathematical Physics. 2022

Statistical Mechanics, Rigorous Results, second Edition.  Ruelle. 1999

I will give an overview of the relationship between phase transitions in spin models on random graphs and the existence of computational thresholds for approximate counting and sampling problems.  In particular, I will explain the results of Weitz and Sly that together show that the uniqueness threshold for the hard-core model on the infinite d-regular tree marks a computational threshold for approximately sampling from the hard-core model on graphs of maximum degree d. More generally, I'll discuss the central role that spin models on infinite trees play in algorithms, statistical physics, and combinatorics.

References:

Textbook for background: Mezard and Montanari, Information, Physics, and Computation: https://web.stanford.edu/~montanar/RESEARCH/book.html

Survey article: Krzakala and Zdeborova, Statistical Physics of Inference: https://arxiv.org/abs/1511.02476

Papers: 

Weitz: Counting Independent Sets up to the Tree Threshold: https://www.drorweitz.com/ac/pubs/ind_from_tree.pdf

Sly: Computational transition at the uniqueness threshold : https://arxiv.org/abs/1005.5584

Coja-Oghlan, Krzakala, Perkins, Zdeborova, Information theoretic thresholds from the cavity method: https://arxiv.org/abs/1611.00814

I will describe the concept of replica symmetry breaking and how it relates to the cavity method from statistical physics used to make precise predictions about phase transitions in spin models and computational problems on random graphs.  I will show how taking the perspective of statistical inference allows us to make parts of the cavity method rigorous. 

 I will give an overview of a project over the last 10 years, joint with L. Sadun et al., of how large-scale structures, ‘phases’, emerge from competing constraints on some large combinatorial systems. The talk will concentrate on the case of constrained dense graphs, but, time permitting, constrast will be noted with phases in constrained sphere packing.

This talk will be an update on the following survey from 5 years ago; in particular I will indicate which open problems have been solved, and which remain.

C. Radin, Phases in large combinatorial systems, Ann. Inst. H. Poincare D 5 (2018) 287-308

We provide an autonomous characterization of the limiting empirical measure of interacting particle systems on locally tree-like (random) graphs.  In particular, we show that unimodularity of the limit random graph allows for a simpler characterization. We also contrast the resulting characterization with commonly used mean-field approximations, which are provably accurate only on dense graphs.  

References (though they are not needed to understand the talk):

1) and 2b) provide background on local convergence; 4) on unimodularity; 2a) and 3) on interacting particle systems

1) Chapter 3 of Lecture notes on random graphs and probabilistic combinatorial optimization, Charles Bordenave, 2016

         https://www.math.univ-toulouse.fr/~bordenave/coursRG.pdf

2a) Local weak convergence for sparse networks of interacting processes, D. Lacker, K. Ramanan and R. Wu, Annals of Applied Probability, 33(2): 843-888, 2023.

https://projecteuclid.org/journals/annals-of-applied-probability/volume-33/issue-2/Local-weak-convergence-for-sparse-networks-of-interacting-processes/10.1214/22-AAP1830.short

2b) see also Appendix A of the following earlier version for a quick recap of local convergence

https://arxiv.org/pdf/1904.02585v1.pdf

3) Marginal dynamics of interacting diffusions on unimodular Galton-Watson trees, D. Lacker, K. Ramanan and R. Wu, Preprint, 2020, https://arxiv.org/abs/2009.11667

   4)   Process on Unimodular Networks, D. Aldous and R. Lyons, EJP, 12, 1454-1508 (2007).

https://projecteuclid.org/journals/electronic-journal-of-probability/volume-12/issue-none/Processes-on-Unimodular-Random-Networks/10.1214/EJP.v12-463.full

Nonamenability creates problems in entropy theory: the most natural way of defining an "entropy rate" of a measure-preserving system fails to be isomorphism-invariant, and also fails to behave well in some settings related to statistical physics. I will explain how sofic entropy solves some of these problems.

References:

• A brief introduction to sofic entropy theory, by Lewis Bowen: https://arxiv.org/abs/1711.02062

• Free Energy, Gibbs Measures, and Glauber Dynamics for Nearest-neighbor Interactions on Trees, by C. Shriver: https://arxiv.org/abs/2011.00653

The local behavior of typical solutions of random constraint satisfaction problems (CSP) describes many important phenomena including clustering thresholds, decay of correlations, and the behavior of message passing algorithms.  When the constraint density is low, studying the planted model is a powerful technique for determining this local behavior which in many examples has a simple Markovian structure. Work of Coja-Oghlan, Kapetanopoulos, Müller (2020) showed that for a wide class of models, this description applies up to the so-called condensation threshold.  

Understanding the local behavior after the condensation threshold is more complex due to long-range correlations. In this joint work with Allan Sly, we revisit the random regular NAE-SAT model in the condensation regime and determine the local weak limit which describes a random solution around a typical variable. This limit exhibits a complicated non-Markovian structure arising from the space of solutions being dominated by a small number of large clusters, a result rigorously verified by Nam, Sly, Sohn (2021).  This is the first characterization of the local weak limit in the condensation regime for any sparse random CSP's in the one-step replica symmetry breaking (1RSB) class. Our proof is based on coupling the local neighborhoods of an infinite spin system, which encodes the structure of the clusters, to a broadcast model on trees whose channel is given by the 1RSB belief-propagation fixed point.

Suggested list of references for the talk:

1. 'Satisfiability Threshold for Random Regular NAE-SAT' by Jian Ding, Nike Sun, Allan Sly, Communications in Mathematical Physics, 2016

2. 'The number of solutions for random regular NAE-SAT' by Allan Sly, Nike Sun, Yumeng Zhang, Probability Theory and Related Fields, 2022

3. 'One-step replica symmetry breaking of random regular NAE-SAT I' by Danny Nam, Allan Sly, Youngtak Sohn, arXiv preprint:2011.14270, 2021

Consider the plus state of the Ising model at very low temperature on some graph. Does it stochastically dominate a high-density Bernoulli percolation? The answer depends drastically on the geometry of the graph. We'll discuss this and other questions of stochastic domination, and how amenability or lack thereof plays a crucial role.

A process is a finitary factor of iid if it can be written as a measurable and equivariant function of an iid process. Van den Berg and Steif showed that the plus state of the Ising model on an amenable graph is a finitary factor of iid if and only if it coincides with the minus state. In sharp contrast, we show that it is a finitary factor of iid at very low temperatures on a nonamenable graph.

Joint work with Gourab Ray.

Reference:

Characterizations of amenability through stochastic domination and finitary codings. https://arxiv.org/abs/2304.13784

The Boltzmann distribution is used in statistical mechanics to describe the distribution of states in systems with a given temperature. We give a novel characterization of this distribution as the unique one satisfying independence for uncoupled systems. The theorem boils down to a statement about symmetries of the convolution semigroup of finitely supported probability measures on the integers.

Joint with Fedor Sandomirskiy.