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?



What is $\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T Z \sigma]$ for a random Gaussian matrix $Z$?
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}).
$$


