What is $\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T Z \sigma]$ for a random Gaussian matrix $Z$? Given an $n \times n$ random matrix $\mathbf{Z}$ with each entry i.i.d. $\mathcal{N} (0,1)$, what is $\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T Z \sigma]$ as $n \to \infty$? If this is too much to ask, are there any good known upper or lower bounds?
 A: This is related to the Sherrington-Kirkpatrick Spin Glass model. In arxiv.org/pdf/1412.0170.pdf, Dmitry Panchenko writes that
$$\lim_{N\to\infty} \frac{1}{N} \mathbb{E}\big[\max_\sigma \frac{1}{\sqrt{N}} \sum_{i<j} g_{ij} \sigma_i \sigma_j \big] \approx 0.7633$$
with $g_{ij}$ iid standard normals. This is a consequence of the Parisi formula. I believe your desired asymptotic should then be $0.7633\sqrt{2}N^{3/2}+ o(N^{3/2})$.
A: This gives a lower bound of $\frac{4}{3\sqrt{\pi}}n^{3/2}+O(\sqrt{n})$ and an upper bound of $2n^{3/2}+O(\sqrt{n})$. Note: in the arguments below, I messed up the constants somewhere, so I'm not sure what the correct constants they should give is. The arguments should still work.
To get a lower bound, we can try to build $\sigma$ greedily. Choose $\sigma_1$ arbitrarily, and choose $\sigma_j$ depending on $\{\sigma_i,Z_{ij},Z_{ji}\mid i<j\}$. When we are choosing $\sigma_j$, we are trying to maximize
$$
\sigma_j\sum_{i<j} \sigma_i(Z_{ij}+Z_{ji}).
$$
Since all the $Z_{ij}$ and $Z_{ji}$ are iid $\mathcal N(0,1)$ independent of $\{\sigma_i\mid i<j\}$, we get that $\sum_{i<j} \sigma_i(Z_{ij}+Z_{ji})\sim \mathcal N(0,2(j-1))$, so by the right choice of $\sigma_j$, we can get 
$$
\mathbb E\left[\sigma_j\sum_{i<j} \sigma_i(Z_{ij}+Z_{ji})\right]=\sqrt{2(j-1)}\sqrt{2/\pi}=\frac{2}{\sqrt{\pi}}\sqrt{j-1}
$$
where $\sqrt{2/\pi}=\mathbb E|x|$ for $x\sim \mathcal N(0,1)$.
Finally, we get
$$
\mathbb E[ \sigma^TZ\sigma]=E\left[\sum_{i=1}^n Z_{ii}\sigma_i^2+\sum_{j=1}^n \sigma_j\sum_{i<j} \sigma_i(Z_{ij}+Z_{ji})\right]=\frac{2}{\sqrt{\pi}}\sum_{j=1}^n \sqrt{j-1}
$$
I'm sure there are more precise ways to evaluate the last sum, but just comparing it to Riemann sums from above and below, we can get
$$
\sum_{j=1}^n \sqrt{j-1}=n^{3/2}\int_0^1\sqrt{x} dx+O(\sqrt{n})=\frac{2}{3}n^{3/2}+O(\sqrt{n})
$$
putting it all together, this greedy construction yields a lower bound of
$$
\mathbb E[ \sigma^TZ\sigma]\ge  \frac{4}{3\sqrt{\pi}}n^{3/2}+O(\sqrt{n})
$$
for well-chosen $\sigma$ (hopefully I didn't mess up the coefficient in front).
To get the upper bound, we note that for any fixed $\sigma$, we have that $\sigma^TZ\sigma\sim \mathcal N(0,n^2)$, so (this is not using optimal bounds on erf)
$$
\mathbb P\left[\sigma^TZ\sigma>Cn^{3/2}\right]<\exp\left(-\frac{C^2}{2}n\right)
$$
so, since there are only $2^n$ choices for $\sigma$, we have
$$
\mathbb P\left[\max_\sigma \sigma^TZ\sigma>Cn^{3/2}\right]<\exp\left(\left(2-\frac{C^2}{2}\right)n\right)
$$
Then we use
$$
\mathbb E(\max_\sigma \sigma^TZ\sigma>Cn^{3/2})\le 2n^{3/2}+n^{3/2}\int_{2n^{3/2}}^\infty  \mathbb P(\max_\sigma \sigma^TZ\sigma>s) ds\le n^{3/2}\left(2+\int_{2}^\infty \exp\left(\left(2-\frac{t^2}{2}\right)n\right) dtdt\right)=2n^{3/2}+O(\sqrt{n}).
$$
