Name
Abstract | ||
|---|---|---|
study the problem of computing the $prightarrow q$ norm of a matrix $A R^{m times n}$, defined as [ |A|_{prightarrow q} ~:=~ max_{x ,in, R^n setminus {0}} frac{|Ax|_q}{|x|_p} ] 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 regimes. When $p geq 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 notin [q,p]$. The regime when $p 2$ was studied by [Barak et al, STOCu002712] 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 u003c q$. We study the hardness of approximating matrix norms in both the above cases and prove the following results: - show that for any $1u003c p u003c q u003c infty$ with $2 notin [p,q]$, $|A|_{prightarrow q}$ is hard to approximate within $2^{O(log^{1-epsilon}!n)}$ assuming $NP notsubseteq BPTIME(2^{log^{O(1)}!n})$. This suggests that, similar to the case of $p geq q$, the hypercontractive setting may be qualitatively different when $2$ does not lie between $p$ and $q$. - For all $p geq q$ with $2 [q,p]$, we show $|A|_{prightarrow q}$ is hard to approximate within any factor than $1/(gamma_{p^*} cdot gamma_q)$, where for any $r$, $gamma_r$ denotes the $r^{th}$ norm of a gaussian, and $p^*$ is the dual norm of $p$. |
Year | Venue | Field |
|---|---|---|
2018 | Electronic Colloquium on Computational Complexity (ECCC) | Approximation algorithm,Discrete mathematics,Combinatorics,Polynomial,Matrix (mathematics),Hardness of approximation,Matrix norm,Gaussian,Mathematics,Exponential time hypothesis,Dual norm |
DocType | Volume | Citations |
Journal | 25 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vijay V. S. P. Bhattiprolu | 1 | 1 | 3.06 |
| Mrinal Kanti Ghosh | 2 | 2 | 2.75 |
| V. Guruswami | 3 | 3205 | 247.96 |
| Euiwoong Lee | 4 | 47 | 15.45 |
| Madhur Tulsiani | 5 | 358 | 24.60 |