Schedule for: 24w5169 - Frontiers of Statistical Mechanics and Theoretical Computer Science

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

The cluster expansion is a classical and powerful tool in the rigorous study of statistical mechanics. More recently it has enjoyed numerous applications in the fields of combinatorics and approximate counting/sampling. In this talk, I will give an introduction to the cluster expansion and discuss some of these new developments.

1. Corrine Yap 2. Dylan Altschuler 3. Ewan Davies 4. Gourab Ray 5. Nitya Mani 6. Vishesh Jain 7. Laura Eslava 8. Elizabeth Collins-Woodfin 9. Gerandy Brito 10. Guus Regts

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

I will give a survey on recent connections developed between the rapidly growing area of high dimensional expanders and analysis of mixing time of Markov chains. I will then discuss application to several classical counting and sampling problems such as sampling bases of matroids, independent sets, and proper edge coloring of graphs. I will conclude the talk by explaining several avenues of future research.

1. Candida Bowtell 2. Holden Lee 3. Joseph Chen 4. Michael Molloy 5. Sarah Cannon 6. Edward Zeng 7. Charlie Carlson 8. Raimundo Briceño 9. Thuy-Duong (June) Vuong 10. Saraí Hernández-Torres

Mean field spin glasses are a family of random functions in high dimension. Originally developed to explore properties of disordered magnets, these models have found applications to a broad range of problems in computer science and statistics. Parisi's theory of replica symmetry breaking predicts the global maximum value of these functions. In many setting, this has been rigorously confirmed by Talagrand and others. What about efficient algorithms? Namely, given a random high-dimensional optimization problem, can one efficiently compute an approximately optimal solution? What about sampling a uniformly random solution? I will review recent progress on this class of problems.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

The hypergraph container lemma is a powerful tool in probabilistic combinatorics that has found many applications since it was first proved a decade ago. Roughly speaking, it asserts that the family of independent sets of every uniform hypergraph can be covered by a small number of almost-independent sets, called containers. In this talk, I will present two new versions of the hypergraph container lemma that utilise alternative notions of almost-independence, in place of the usual 'balanced supersaturation' property. The two lemmas display a number of other attractive features and have surprising connections to several other well-studied topics in probabilistic combinatorics. This is joint work with Marcelo Campos (Cambridge).

We will discuss the typical behavior of M-Lipschitz functions on d-regular expander graphs, where an M-Lipschitz function means any two adjacent vertices admit integer values differ by at most M. While it is easy to see that the maximum possible height of an M-Lipschitz function on an n-vertex expander graph is about C*M*log n, where C depends (only) on d and the expansion of the given graph, it was shown by Peled, Samotij, and Yehudayoff (2012) that a uniformly chosen random M-Lipschitz function has height at most C'*M*loglog n with high probability, showing that the typical height of an M-Lipschitz function is much smaller than the extreme case. Peled-Samotij-Yehudayoff's result holds under the condition that, roughly, subsets of the expander graph expand by the rate of about M*log(dM). We will show that the same result holds under a much weaker condition assuming that d is large enough. This is joint work with Robert Krueger and Lina Li.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

The binary perceptron problem asks us to find a sign vector in the intersection of independently chosen random halfspaces with a fixed intercept. The computational landscape of the binary perceptron is not yet well-understood. In some regimes there may be an information-computation gap, but there is much room for improvement on both the algorithms and lower-bounds side. In this talk I will discuss a forthcoming work in which we analyze the performance of canonical discrepancy minimization algorithms for the binary perceptron problem, obtaining new algorithmic results with simple off-the-shelf algorithms and relatively simple analysis. In some settings, we complement these algorithmic results with (close, but non-matching) overlap-gap lower bounds. This is based on joint work with Tselil Schramm and Kangjie Zhou.

The approximate message passing (AMP) framework has been widely successful at producing algorithms with provable guarantees for a variety of high-dimensional statistical inference tasks. In some settings, AMP is conjectured to be optimal in the sense that no computationally efficient estimator can achieve a better mean squared error (MSE). In a simple "signal plus noise" model (spiked Wigner), we prove a variant of this conjecture by showing that AMP has the best possible MSE within a larger class of algorithms, namely those that can be described as constant-degree polynomials. This is joint work with Andrea Montanari, available at: https://arxiv.org/abs/2212.06996

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

Fix a graph G and a starting vertex r (the root), and let T be a spanning tree of G grown as follows. Initially, vertex r is infected and all other vertices are susceptible. At constant rate, each infected node infects each neighbouring susceptible node. Eventually, all vertices are infected; the edge set of T is the set of edges along which the infection spread. How easy is it to recover the identity of the initially infected individual r if one is given access to T? I will discuss recent work on this problem when G is a random graph with a fixed degree sequence. Along the way, it is also useful to consider the case when G is an infinite tree. Based on joint work with Sasha Bell, Tasmin Chu, Théodore Conrad-Frenkiel, Catherine Fontaine, Robin Khanfir, and Simone Têtu

Sudden emergence of a giant component discovered by Erd\H{o}s and R\'enyi concerns random subgraphs defined in terms of Bernoulli percolation on the complete graph $K_n$. Similar results were obtained in other instances of percolation on various finite graphs. In particular, the case of percolative random subgraphs of $n$-cube $Q_n$ was treated by Ajtai, Komlós, and Szemerédi. Surprisingly, the only result concerning emergence of a giant component when percolation is replaced by a random cluster measure has been obtained in the case of the complete graph by Bollobás, Grimmett, and Janson. While formulating our results and some hints of proofs, I will touch several related topics: Potts model and its mean field limit, Edwards-Sokal coupling, sprinkling for random cluster measures, and motivations from statistical physics via weighted random interchange on $Q_n$. Based on joint work with Darion May.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

I will discuss how to speed up sampling from an arbitrary distribution on a product space [q]^n, given oracle access to conditional marginals, as in any-order autoregressive models. The algorithm takes n^{2/3} polylog(n, q) parallel time, the first sublinear-in-n bound for arbitrary distributions. We also show a lower bound of n^{1/3} on the parallel runtime of any algorithm, putting the complexity firmly in the sublinear but polynomially large territory. Joint work with Aviad Rubinstein and Ruiquan Gao.

Consider random configurations of disjoint disks of euclidean diameter D centered on integer coordinates in a bounded domain, where the probability for the appearance of a configuration is proportional to λⁿ, with n being the number of tiles in the configuration. This is a special case of the Hard-core model in statistical physics. We are interested in characterizing the periodic Gibbs measures for sufficiently large values of λ. For all but a finitely many cases for D, this was solved recently by Mazel, Stuhl and Suhov. The remaining cases seem to display a variety of interesting behaviours. We solved the case D=2, using Reflection Positivity. I will present ideas from our proof, and some initial thoughts (and MCMC simulations) for the remaining open cases. Based on a joint work with Ron Peled.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Many low-temperature dynamics in complex landscapes are expected to exhibit a sharp form of metastability, where the state space can be partitioned into wells, such that the equilibration time within each well is much faster than the transit time between wells, and the process tracking which well the Markov chain belongs to, itself is asymptotically Markovian. We overview this predicted picture for mean-field spin glass dynamics, its relation to aging predictions, and then describe recent results with Curtis Grant proving this for Glauber dynamics for mean-field heavy-tailed spin glasses.

Programmable matter explores how collections of computationally limited agents acting locally and asynchronously can achieve useful coordinated behaviors. We take a stochastic approach using techniques from randomized algorithms and equilibrium statistical physics to develop distributed algorithms for emergent collective behaviors that give guarantees and are robust to failures. We will also introduce some new tools that may prove fruitful in nonequilibrium settings as well.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

We consider the frog model on either Z^d or the torus. At each site there are initially a Poisson number of sleeping frogs. When an active frog visits a site, all frogs there wake up, perform a random walk for some time, and die. In this work, our random walks are heavy tailed. We connect this model with long range percolation, and derive estimates for the hitting time of a vertex and the cover time of the torus. Joint with Jonathan Hermon and Yuliang Shi

5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM.

We consider the problem of efficiently optimizing the random (spherical or Ising) perceptron model with general bounded Lipschitz activation. We focus on a class of algorithms with Lipschitz dependence on the disorder, which includes constant-order methods such as gradient descent, Langevin dynamics, and AMP on dimension-free time-scales. Our main result exactly characterizes the optimal value ALG such algorithms can attain in terms of a 1-dimensional stochastic control problem. Qualitatively, ALG is the largest value whose level set contains a certain "dense solution cluster." Quantitatively, this characterization yields both improved algorithms and hardness results for a variety of asymptotic regimes, which are sharp up to absolute constant factors. Based on joint work with Mark Sellke and Nike Sun.