Rademacher matrix norm conjecture

Let $(a_{ij})_{i,j\leq n}$ be real coefficients, and let $(\varepsilon_{ij})_{1\leq i,j\leq n}$ be independent symmetric random variables taking values in $\{-1,1\}$. For a random matrix, write $\|\cdot\|$ for its operator norm, and let $\|S\|_p=({\mathbb E}|S|^p)^{1/p}$.

Rademacher matrix norm conjecture. We have

$$\begin{aligned} {\mathbb E}\|(a_{ij}\varepsilon_{ij})_{i,j\leq n}\| &\sim \max_{1\leq i\leq n}\left(\sum_{j=1}^n a_{ij}^2\right)^{1/2}+\max_{1\leq j\leq n}\left(\sum_{i=1}^n a_{ij}^2\right)^{1/2} \\ &\phantom{=} +\max_{1\leq k\leq n}\min_{I\subset [n],|I|\leq k} \sup_{\|s\|_2,\|t\|_2\leq 1}\left\|\sum_{i,j\notin I}a_{ij}\varepsilon_{ij}s_it_j\right\|_{\log (k+1)}. \end{aligned}$$

This conjecture seeks a matching upper bound for the proved lower bound on the expected operator norm of a Rademacher matrix; the paper presents it as an open problem.