# Algorithmic Methods from Statistical Physics

## Day-1 (02/01/2022)

1. <u>The SK Model</u>:
* The model is the starting point of Spin-Glass Theory, and roughly speaking asks for the $\mathsf{MAX}$-$\mathsf{CUT}$ of a typical instance of the complete graph with i.i.d. gaussian weights.
* Formally speaking, this is represented as the following problem:
$$
\lim_{n \to \infty}\frac{1}{n}\mathbb{E}_g\left[\max_{\sigma \in \{\pm 1\}^n}H_n(\sigma)\right]\, ,
$$
where the hamiltonian $H_n(\sigma)$ represents the normalized quadratic form over the gaussian matrix $G \sim GOE(n)$,
$$
H_n(\sigma) = \frac{1}{\sqrt{n}}\langle \sigma, H \sigma \rangle\, .
$$
Each entry of $G$ is i.i.d. $\mathcal{N}(0, 1)$. The $\frac{1}{n}$ normalization is included so that the limit is well-defined (does not depend on $n$) and this can be shown by analyzing the auto-covariance of the centered gaussian stochastic process $\{H_n(\sigma)\}_{\sigma \in \{\pm 1\}^n}$.
* Note that the covariance (which basically measures the "correlation" between the desired statistic under two different assignments) of the stochastic process will tell us how much one can expect two different assignments $\sigma_1$ and $\sigma_2$ to cause $H_n(\sigma)$ to fluctuate, which will in-turn tell us the order of the maximum as a function of $n$. This will hint at the appropriate normaliztion of the statistic.
* <u>Lemma-1 [Covariance & Overlap]</u>: The autocovariance of a centered gaussian process with variance $1$ is,
$$
\mathbb{E}[H_n(\sigma_1)H_n(\sigma_2)] = n\cdot\left(\frac{1}{n}R_{1,2}\right)^2\, ,
$$
where $R_{1,2}$ denotes the overlap between any two assignments $\sigma_1$ and $\sigma_2$,
$$
R_{1,2}(\sigma_1, \sigma_2) = \langle\sigma_1, \sigma_2\rangle\, .
$$
The lemma above makes it clear that $\frac{1}{n}$ is the correct normalization to well-define the limit of the statistic under consideration.
* It's straightforward to see that $\mathbb{E}[H_n(\sigma)] = 0$, and this reveals that the process in consideration is centered.
* We now represent the statistic under consideration by its smoothed approximation (which in physics is the equivalent of re-writing the problem in terms of its _Free Energy density_). To that end, note the following,
$$
\frac{1}{n}\mathbb{E}\left[\max_{\sigma \in \{\pm 1\}^n}H_n(\sigma)\right] \leq \frac{1}{\beta n}\mathbb{E}\left[\sum_{\sigma \in \{\pm 1\}^n}e^{\beta H_n(\sigma)}\right] \leq \frac{1}{\beta n}\mathbb{E}\left[\max_{\sigma \in \{\pm 1\}^n}H_n(\sigma)\right] + \frac{\log(2)}{\beta}\, ,
$$
which holds for all $\beta > 0$.
2. <u>The Parisi Variational Principle</u>:
* The main claim here is that, analogous to a LLN-type statement, the $\mathsf{MAX}$-$\mathsf{CUT}$ statistic of $H_n(\sigma)$ can be be described by, instead of some _fixed_ random varaible $X$, a variational principle optimized over the space of all Cumulative Distribution Functions.
* <u>Theorem-1 [Pa'79, Pa'80, Ta'06, Pa'13]</u>: The limit of the ground-state energy of the SK model is described as follows,
$$
\lim_{n \to \infty}\frac{1}{n}\mathbb{E}_g\left[\max_{\sigma \in \{\pm 1\}^n}H_n(\sigma)\right] = \lim_{\beta \to \infty}\inf_{\mu \in \mathsf{CDF}([0, 1])} \frac{1}{\beta}\mathcal{P}_\beta(\mu)\, ,
$$
where the functional is given by,
$$
\mathcal{P}_\beta(\mu) = \Phi_\mu(0, 0) - \frac{\beta^2}{2}\int_{0}^1 t\mu(t) dt\, ,
$$
and $\Phi_\mu(x, t)$ is a "free-entropy" quantity that comes from the solution of the following hyperbolic differential equation,
$$
\partial_t\Phi_\mu(x, t) = -\frac{\beta^2}{2}(\partial_{xx}\Phi_\mu(x, t) + \mu(t)\cdot(\partial_x\Phi_\mu(x, t))^2)\, ,
$$
with the initial condition,
$$
\Phi_\mu(x, 1) = \log(2\cosh(x))\, .
$$
* A few comments about the theorem above are in order:
* The parameters $x$ and $t$ correspond to the so-called cavity-field around a vertex and the overlap of solutions respectively. This may seem vague now, but this interpretation will become clearer as we construct the proof for Theorem-1 over the next couple of weeks.
* The second term in the Parisi functional $\mathcal{P}_\beta(\mu)$ corresponds to the _variance_ of the overlap $t$, and this can be made clear by the observations that,
$$
\mu_t = \Pr[|\langle \sigma_1, \sigma_2 \rangle| \leq t] = 1 - \Pr[|\langle \sigma_1, \sigma_2 \rangle| \geq t]\, ,
$$
and that
$$
\mathbb{E[|\langle \sigma_1, \sigma_2 \rangle|^p]} = \int_{0}^1pt^{p-1}Pr[|\langle \sigma_1, \sigma_2 \rangle| \geq t]dt\, ,
$$
which in turn immediately imply that,
$$
\int_0^1t\mu(t)dt = \frac{1}{2}(1 - \mathbb{E}[\langle \sigma_1, \sigma_2 \rangle^2])\, ,
$$
leading to the following formulation of the Parisi Variational Principle,
$$
\mathcal{P}_\beta(\mu) = \Phi_\mu(0, 0) + \frac{\beta^2}{4}(\mathbb{E}[\langle \sigma_1, \sigma_2] - 1)\, .
$$
Note that this implies that the Parisi variational principle attempts to find an overlap distribution $\mu$ which minimizes the variance over the overlaps while _simultaneously_ minimizing the Parisi PDE.
3. <u>Euler-Lagrange Equations: First & Second Variational Form</u>:
* We begin by briefly introducing the Euler-Lagrange Equations and how they correspond to the first variational form and determine the stationary point of a functional $\mathcal{I}$.
4. <u>Hamilton-Jacobi Equations</u>:
* We begin by stating and deriving Hamilton's principle and then stating the Hamilton-Jacobi equations.

## Day-2 (02/08/2022)