Seminars
View all Seminars | Download ICal for this eventApproximability of p q Matrix Norms:Some NP-hardness Results and An Approximation Algorithm
Series: Bangalore Theory Seminars
Speaker: Mrinalkanti Ghosh Indian Institute of ScienceBangalore
Date/Time: Sep 23 11:00:00
Location: CSA Seminar Hall (Room No. 254, First Floor)
Abstract:
A real n x m matrix A represents a linear map from $R^m$ to $R^n$. If the domain and the range of the map is endowed with $ell_p$-norm and -norm respectively, then we can measure the "stretch" of the map A. Thus matrix p->q-norm of a matrix A is defined to be $sup_{xin R^n, ||x||_ple 1} || Ax ||_q$. This quantity generalizes the well known spectral norm which is very useful in many areas of theoretical computer science (and that of mathematics). This can also be seen as a special case of optimizing a polynomial over a convex body. When $p<q$, we call this problem hypercontractive matrix norm estimation, and the case of $p ge q$ is called reverse-hypercontractive matrix norm estimation. The placement of 2 with respect to the interval $p$ to $q$ turns out to be of importance in approximability or inapproximability of the problem.
The case of $infty to 1$-norm was studied by Grothendieck in his famous Resume (1956). The integrality gap of an SDP relaxation for this problem is a constant, called Grothendiecks constant. The combinatorial quantity cut-norm of a graph is related to the $infty to 1$-norm of the adjacency matrix of the graph, as observed by Alon and Naor (2004). Therefore, this problem has relevance in combinatorial optimization problems . NP-hardness of the $inftyto 1$ problem was established by Bri?«t, Regev and Saket (2015) within the constant $pi/2$ for the special case of positive semidefinite matrix. Constant factor approximation algorithms for the case $2in [q,p]$ were developed by Nesterov (1998) and Steinberg (2005). For the case $2 not in [q,p]$, quasi-polynomial hardness was shown by Bhaskara and Vijayaraghavan (2015) assuming NP does not have quasi-polynomial time algorithms.
The problem of the $2to 4$ norm is relevant in several problems in quantum information theory (as shown in work of Harrow and Montanaro (2013)). Barak et.al. (2012) showed that the $2to q$-norm estimation problem (for even $qge 4$) is intimately related to the problem of Small Set Expansion. They also proved a hardness of approximation assuming Exponential Time Hypothesis.
We proved the first NP hardness of the hypercontractive norm in case $2notin [p,q]$. We show quasi-polynomial hardness of approximation assuming NP does not have quasi-polynomial time randomized algorithms. For the reverse-hypercontractive case of $2in [q,p]$, we proved NP hardness of approximation within a constant ($1/(gamma_q gamma_{p*})$) factor. In an associated work we gave an algorithm with approximation factor constant away from the above -- that is the dependency on $p$ and $q$ on the hardness factor is roughly correct. We also recovered the hardness result of Bhaskara and Vijayaraghavan (2015) for the reverse-hypercontractive $2 not in [q,p]$ case, albeit under slightly stronger hardness assumption. All of our hardness results follow a general framework.
Based on joint work with Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee, and Madhur Tulsiani. Appeared in SODA 2019.
For more details please visit: Link
Microsoft teams link:
Link