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.

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.

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.

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.

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.

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.

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.