We study the problem of computing the p q norm of a matrix A R m n , defined as A p q : = max x R n 0 x p Ax q This problem generalizes the spectral norm of a matrix ( p = q = 2 ) and the Grothendieck problem ( p = , q = 1 ), and has been widely studied in various regimes. When p q , the problem exhibits a dichotomy: constant factor approximation algorithms are known if 2 [ q p ] , and the problem is hard to approximate within almost polynomial factors when 2 [ q p ] .

The regime when p is less than q , known as hypercontractive norms, is particularly significant for various applications but much less well understood. The case p = 2 and 2"> q 2 was studied by [Barak et al, STOC'12] who gave sub-exponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the Exponential Time Hypothesis. However, no NP-hardness of approximation is known for these problems for any p q .

We study the hardness of approximating matrix norms in both the above cases and prove the following results:

- We show that for any 1 p q with 2 [ p q ] , A p q is hard to approximate within 2 O ( log 1 − n ) assuming N P B PTIM E ( 2 log O (1) n ) . This suggests that, similar to the case of p q , the hypercontractive setting may be qualitatively different when 2 does not lie between p and q .

- For all p q with 2 [ q p ] , we show A p q is hard to approximate within any factor smaller than 1 ( p q ) , where r denotes the r th norm of the standard Gaussian, and p is the dual norm of p .