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

Beginning on Sunday, August 11 and ending Friday August 16, 2024

All times in Banff, Alberta time, MDT (UTC-6).

Sunday, August 11 | |
---|---|

16:00 - 17:30 | Check-in begins at 16:00 on Sunday and is open 24 hours (Front Desk - Professional Development Centre) |

17:30 - 19:30 |
Dinner ↓ A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building. (Vistas Dining Room) |

20:00 - 22:00 | Informal gathering (TCPL Foyer) |

Monday, August 12 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

08:45 - 09:00 |
Introduction and Welcome by BIRS Staff ↓ A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions. (TCPL 201) |

09:00 - 10:00 |
Matthew Jenssen: Applications of the cluster expansion ↓ 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. (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:30 |
Lightning Talks 1 ↓ 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 (TCPL 201) |

11:30 - 13:00 |
Lunch ↓ Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

13:00 - 14:00 |
Shayan Oveis Gharan: The MCMC method and High Dimensional Expanders ↓ 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. (TCPL 201) |

14:00 - 15:00 |
Lightning Talks 2 ↓ 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 (TCPL 201) |

15:00 - 15:30 | Coffee Break (TCPL Foyer) |

15:30 - 16:30 |
Mark Sellke: Algorithmic Spin Glass Theory ↓ 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. (TCPL 201) |

17:30 - 19:30 |
Dinner ↓ A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building. (Vistas Dining Room) |

Tuesday, August 13 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

09:00 - 10:00 |
Wojciech Samotij: The hypergraph container lemma revisited ↓ 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). (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:30 |
Jinyoung Park: Lipschitz functions on expanders ↓ 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. (TCPL 201) |

11:30 - 11:45 | Group Photo (Online) |

11:30 - 13:00 |
Lunch ↓ Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

14:00 - 15:00 |
Shuangping Li: Discrepancy algorithms for the binary perceptron ↓ 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. (TCPL 201) |

15:00 - 15:30 | Coffee Break (TCPL Foyer) |

15:30 - 16:30 |
Alex Wein: Optimality of AMP Among Low-Degree Polynomials ↓ 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 (TCPL 201) |

17:30 - 19:30 |
Dinner ↓ A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building. (Vistas Dining Room) |

Wednesday, August 14 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

09:00 - 10:00 |
Louigi Addario-Berry: The top eigenvalue of random trees ↓ Let $T_n$ be a uniformly random tree with vertex set $[n]={1,…,n}$. Let $Delta_n$ be the largest vertex degree in $T_n$ and let $\lambda_n$ be the largest eigenvalue of $T_n$. We show that $|\lambda_n-\sqrt{\Delta_n}| \to 0$ in probability as $n \to \infty$. The key ingredients of our proof are (a) the trace method, (b) a rewiring lemma that allows us to “clean up” our tree without decreasing its top eigenvalue, and (c) some careful combinatorial arguments.
This is joint work with Roberto Imbuzeiro Oliveira and Gabor Lugosi. (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:30 |
Roman Kotecky: Emergence of a giant component for random cluster model on the n-cube ↓ 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. (TCPL 201) |

11:30 - 13:00 |
Lunch ↓ Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

13:30 - 17:30 | Free Afternoon (Banff National Park) |

17:30 - 19:30 |
Dinner ↓ |

Thursday, August 15 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ |

09:00 - 10:00 |
Nima Anari: Parallel Sampling via Counting ↓ 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. (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:30 |
Daniel Hadas: Random high-density packing of disks on a lattice ↓ 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. (TCPL 201) |

11:30 - 13:00 |
Lunch ↓ |

14:00 - 15:00 |
Reza Gheissari: Metastability in heavy-tailed spin glass dynamics ↓ 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. (TCPL 201) |

15:00 - 15:30 | Coffee Break (TCPL Foyer) |

15:30 - 16:30 |
Dana Randall: Emergent phenomena in equilibrium and nonequilibrium collectives ↓ 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. (TCPL 201) |

17:30 - 19:30 |
Dinner ↓ |

Friday, August 16 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ |

09:00 - 10:00 | Omer Angel (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:00 |
Checkout by 11AM ↓ 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. (Front Desk - Professional Development Centre) |

10:30 - 11:30 |
Brice Huang: Algorithmic threshold for the random perceptron ↓ 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. (TCPL 201) |

12:00 - 13:30 | Lunch from 11:30 to 13:30 (Vistas Dining Room) |