HW #1: How does the Boltzmann distribution arise? A nice explanation is provided here.

HW #2: Fix p> 0.

(i) Show that an Erdos-Renyi graph with edge probability p=k/n converges locally weakly to a Galton Watson tree with degree distribution Poisson(k) as n \to \infty.

(ii) Consider a GW tree with degree distribution Poisson(k). Use density evolution (recursion) to characterize the likelihood the tree grows to depth at least t. Infer that the probability \pi of growing to infinite depth is positive if and only if k>1. And that for k>1, \pi is the positive solution of \pi = 1 - exp(-\pi k).

Learning the meaning of the terms in the HW is part of your job. Brief defns:

• ER graph: random graph on n nodes where each edge is present iid with probability p.
• GW tree with offspring distribution D: Start with a root node. Draw its number of children from D. For each child, independently draw their number of children from D, and so on recursively to construct a rooted tree.
• weak convergence: convergence in distribution
• local weak convergence: the depth d neighborhood converges weakly, for every d< \infty.
• density evolution: this is a recursive relation of the type we covered in class today.

Fyi: The same condition k>1 shows up for the emergence of a giant component (a connected component with \Omega(n) nodes) in an ER graph whp. This lines up with the GW tree growing to infinite depth as you show in part (ii).

HW#3: Write the max product message passing equations that would end up solving the maximum weight matching problem on trees (but also more generally, it turns out). Once you attempt the question, you can check your answer on page 5 of this paper, for instance.

Follow up after session 8:

As a follow up to the lecture on 11/1 about the CREM (continuous generalization of the GREM), here are some notes:

- the GREM model is due to Derrida

Derrida, B.: A generalization of the random energy model which includes correlations between energies. J. Phys. Lett. 46, L-401-L-407 (1985)

Derrida, B., Gardner, E.: Solution of the generalized random energy model, J. Phys.C. In press (1986)

- The GREM is intended to capture the "universal" geometry of the energy landscape of spin glasses, which, based on Parisi's conjecture, is almost fully specified by the parameter A, which is the defining parameter of the GREM/CREM. Under the CREM, the depth of the most recent common ancestor (divided by N) is a proxy for the overlap.

- The RPC was introduced by Ruelle as a way to make the GREM formal.

David Ruelle, A Mathematical Reformulation of Derrida's REM and GREM, Commun. Math. Phys. 108, 225-239 (1987).

The RPC captures the geometry of the Boltzmann measure at a given \beta. The overlap distribution gets truncated/collapsed at some maximum overlap x_\beta, where x_\beta increases in \beta (i.e., decreases in the temperature).

- The paper I presented was

The algorithmic hardness threshold for continuous random energy models, Louigi Addario-Berry, Pascal Maillard (2018).

- It was followed in quick succession by the following breakthrough papers, which i mentioned towards the end:

Following the ground-states of full-RSB spherical spin glasses, Eliran Subag (2018). https://www.youtube.com/watch?v=Vi9pELg-1mQ Subag built on his own prior work http://www.birs.ca/events/2018/5-day-workshops/18w5036/videos/watch/201810020901-Subag.html

Optimization of the Sherrington-Kirkpatrick Hamiltonian, A. Montanari (2019) https://www.youtube.com/watch?v=kPMYRHyy8V0