The computational complexity of spectral norm of a matrix
The answer to your question is the contents of section 1.3.2, titled "[w]hen $\mathcal{P}_{p,r}$ is known to be difficult". (Here $\mathcal{P}_{p,r}$ is the problem of computing the norm $\|A\|_{p,r} = \sup_{\|x\|_p=1} \|Ax\|_r$.) According to that section, the only cases which are known to be difficult are $\mathcal{P}_{\infty,1},\mathcal{P}_{\infty,2},\mathcal{P}_{2,1}$. For example, $\mathcal{P}_{\infty,1}$ (even restricted to positive semidefinite matrices) is a generalization of MAX CUT. Since $\|B'B\|_{\infty,1} = \|B\|_{\infty,2}^2$, $\mathcal{P}_{\infty,2}$ is also hard. Finally, $\mathcal{P}_{2,1}$ is as hard as $\mathcal{P}_{\infty,2}$ as part of the more general observation (proved in section 1.3.1) that $\mathcal{P}_{p,r}$ is as hard as $\mathcal{P}_{1/(1-1/r), 1/(1-1/p)}$.

The thesis goes on to prove that $\mathcal{P}_{p,r}$ is hard whenever $p &gt; r$ - this is the chapter you were reading (chapter 2).

Section 1.3.1 described some easy cases: $\mathcal{P}_{1,\ast}$, the symmetric $\mathcal{P}_{\ast,\infty}$, and the case that MCH mentioned, $\mathcal{P}_{2,2}$. Section 1.3.3 covers some approximability results, several novel of which are described in section 1.4 and the remaining chapters.

The title of section 1.3.2 appears in the table of contents (page iii) - just a hint for next time.