Open Collections

Description

I will talk aboutthe problem of computing the operator norm of a matrix mapping vectors in the space l_p to l_q, for different values of p and q. This problem generalizes the spectral norm of a matrix (p=q=2) and the Grothendieck problem (p=\infty, q=1), and has been widely studied in various reigmes. When p greater than or equal to q, the problem exhibits a dichotomy: constant factor approximation algorithms are known if 2 lies between p and q, and is hard to approximate within almost polynomial factors otherwise. The regime when q is greater than p, known as the _hypercontractive case_, is particularly significant for various applications but much less well understood. The case with p = 2 and 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 was known for these problems for any p < q. We study the hardness of approximating matrix norms in both the above cases. We prove the following results: - We show that for any p < q, the operator norm of a given matrix is hard to approximate within almost polynomial factors, when 2 does not lie between p and q. This suggests that similar to the non-hypercontrative setting, the case when 2 does not lie between p and q may be qualitatively different. - We also obtain new (constant factor) hardness results in the non-hypercontractive case when q