Following this [question][1] I was thinking about ways to improve the upper bound and came up with the following argument. We want to find an upper bound for 

\begin{equation}
\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T W \sigma]
\end{equation}

where $W$ is a symmetric matrix with independent entries $W_{ij} \sim \mathcal{N}(0,1)$, except for the symmetry condition. This is a slightly different version of the problem mentioned in the link but the argument is analogous. I came across the following [result][2] for gaussian processes

>Let $(X_1, \ldots, X_n)$ and $(Y_1, \ldots, Y_n)$ be gaussian random vectors with $\mathbb{E}(X_i) = \mathbb{E}(Y_i)$ for each $i$. For $1 \leq i,j \leq n$, let $\gamma_{ij}^{X} = \mathbb{E}(X_i - X_j)^2$ and $\gamma_{ij}^{Y} = \mathbb{E}(Y_i - Y_j)^2$, and let $\gamma = \max_{1 \leq i,j \leq n} | \gamma_{ij}^{X} - \gamma_{ij}^{Y}|$. Then 
>
>\begin{equation}
|\mathbb{E}(\max_{1 \leq i \leq n} X_i) - \mathbb{E}(\max_{1 \leq i \leq n} Y_i) | \leq \sqrt{\gamma \log n}.
\end{equation}

I was thinking about applying this result with the random vectors $Y,X \in \mathbb{R}^{2^n}$ s.t. $Y_i = 0$ and $X_i = 2 \sum \limits_{s<t} A_{ij} \sigma_{s}^{i} \sigma_{t}^{i}$ for $1 \leq i \leq 2^{n} $, where $\sigma^{i}$ is the $i$-th hypercube vertex for some ordering of the vertices. 

**Question**: Is the following Argument sound? Did I make a mistake or overlook something?

----------------------------------------------------------------------------

It is clear that $Y$ is a gaussian random vector. I think $X$ is also a gaussian random vector because for any real numbers $\alpha_1, \ldots, \alpha_n$ we have 

\begin{equation}
\alpha_1X_1 + \ldots + \alpha_n X_n = \sum \limits_{s<t} A_{st}(\sum \limits_{i=1}^{n} \alpha_i \sigma_{s}^{i} \sigma_{t}^{i})
\end{equation}

Which is a gaussian random variable. Furthermore we have 

\begin{equation}
\mathbb{E}(\sum \limits_{s<t} A_{st}\sigma_{s}^{i} \sigma_{t}^{i}) = \sum \limits_{s<t} \mathbb{E}(A_{st})\sigma_{s}^{i} \sigma_{t}^{i} = 0 
\end{equation}

and 

\begin{equation}
\gamma_{ij}^{X} = \sum \limits_{s<t}(\sigma_{s}^i \sigma_{t}^i - \sigma_{s}^{j} \sigma_{t}^{j})^2 \leq 2n^2
\end{equation}

Together with $\gamma_{ij}^Y = 0$ we have 

\begin{equation}
\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T W \sigma] \leq \sqrt{2n^2 \log 2^n}
\end{equation}

The right hand side can be simplified to $\sqrt{2\log(2)} n^{3/2}$. If I understood correctly the author of the cited paper uses $\log$ to denote the natural logarithm. This would lead us to an upper bound of the order $\sim 1.177 n^{3/2}$, which is not too far away from the actual value for large $n$ which is $\sqrt{2} \cdot 0.7633 n^{3/2} \sim 1.079 n^{3/2}$.

---------------------------------------------------------------

Thank you very much for your help. 


  [1]: https://mathoverflow.net/questions/345915/what-is-mathbbe-max-sigma-in-pm-1-n-sigmat-z-sigma-for-a-ra
  [2]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.239.5246&rep=rep1&type=pdf