ﻻ يوجد ملخص باللغة العربية
We study the problem of computing the $prightarrow q$ norm of a matrix $A in 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 in [q,p]$, and the problem is hard to approximate within almost polynomial factors when $2 otin [q,p]$. The regime when $p < q$, known as emph{hypercontractive norms}, 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, STOC12] 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 < infty$ with $2 otin [p,q]$, $|A|_{prightarrow q}$ is hard to approximate within $2^{O(log^{1-epsilon}!n)}$ assuming $NP otsubseteq 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 in [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$.
A rainbow $q$-coloring of a $k$-uniform hypergraph is a $q$-coloring of the vertex set such that every hyperedge contains all $q$ colors. We prove that given a rainbow $(k - 2lfloor sqrt{k}rfloor)$-colorable $k$-uniform hypergraph, it is NP-hard to
In this paper, we consider the Target Set Selection problem: given a graph and a threshold value $thr(v)$ for any vertex $v$ of the graph, find a minimum size vertex-subset to activate s.t. all the vertices of the graph are activated at the end of th
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g.,
A rigidity theory is developed for bar-joint frameworks in linear matrix spaces endowed with a unitarily invariant norm. Analogues of Maxwells counting criteria are obtained and minimally rigid matrix frameworks are shown to belong to the matroidal c
We propose COSMA: a parallel matrix-matrix multiplication algorithm that is near communication-optimal for all combinations of matrix dimensions, processor counts, and memory sizes. The key idea behind COSMA is to derive an optimal (up to a factor of