Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms
Vijay Bhattiprolu, Mrinal K. Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani · SIAM Journal on Computing · 2023
Abstract. We study the problem of computing the [Formula: see text] norm of a matrix [Formula: see text], defined as [Formula: see text]. This problem generalizes the spectral norm of a matrix ([Formula: see text]) and the Grothendieck problem ([Formula: see text], [Formula: see text]) and has been widely studied in various regimes. When [Formula: see text], the problem exhibits a dichotomy: constant factor approximation algorithms are known if [Formula: see text], and the problem is hard to approximate within almost polynomial factors when [Formula: see text]. The regime when [Formula: see text], known as hypercontractive norms, is particularly significant for various applications but much less well understood. The case with [Formula: see text] and [Formula: see text] was studied by Barak et al. [ Proceedings of the 44 th Annual ACM Symposium on Theory of Computing, 2012, pp. 307–326], who gave subexponential 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 [Formula: see text]. We prove the first NP-hardness result (under randomized reductions) for approximating hypercontractive norms. We show that for any [Formula: see text] with [Formula: see text], [Formula: see text] is hard to approximate within [Formula: see text] assuming [Formula: see text]. En route to the above result, we also prove almost tight results for the case when [Formula: see text] with [Formula: see text].