Inapproximability of Matrix $p\to q$ Norms

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2

We study the problem of computing the $p\to q$ norm of a matrix $A\in R^{m\times n}$, defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac…