Approximating Operator Norms via Generalized Krivine Rounding

We consider the $(ell_p,ell_r)$-Grothendieck problem, which seeks to maximize the bilinear form $y^T A x$ for an input matrix $A$ over vectors $x,y$ with $|x|_p=|y|_r=1$. The problem is equivalent to computing the $p to r^*$ operator norm of $A$. The case $p=r=infty$ corresponds to the classical Grothendieck problem. Our main result is an algorithm for arbitrary $p,r ge 2$ with approximation ratio $(1+epsilon_0)/(sinh^{-1}(1)cdot gamma_{p^*} ,gamma_{r^*})$ for some fixed $epsilon_0 le 0.00863$. Comparing this with Krivines approximation ratio of $(pi/2)/sinh^{-1}(1)$ for the original Grothendieck problem, our guarantee is off from the best known hardness factor of $(gamma_{p^*} gamma_{r^*})^{-1}$ for the problem by a factor similar to Krivines defect. Our approximation follows by bounding the value of the natural vector relaxation for the problem which is convex when $p,r ge 2$. We give a generalization of random hyperplane rounding and relate the performance of this rounding to certain hypergeometric functions, which prescribe necessary transformations to the vector solution before the rounding is applied. Unlike Krivines Rounding where the relevant hypergeometric function was $arcsin$, we have to study a family of hypergeometric functions. The bulk of our technical work then involves methods from complex analysis to gain detailed information about the Taylor series coefficients of the inverses of these hypergeometric functions, which then dictate our approximation factor. Our result also implies improved bounds for factorization through $ell_{2}^{,n}$ of operators from $ell_{p}^{,n}$ to $ell_{q}^{,m}$ (when $pgeq 2 geq q$)--- such bounds are of significant interest in functional analysis and our work provides modest supplementary evidence for an intriguing parallel between factorizability, and constant-factor approximability.

Inapproximability of Matrix $prightarrow q$ Norms

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$.

Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere

We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x in mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in diverse contexts ranging from tensor and operator norms to graph expansion to quantum information theory. The homogeneous degree $2$ case is efficiently solvable as it corresponds to computing the spectral norm of an associated matrix, but the higher degree case is NP-hard. We give approximation algorithms for this problem that offer a trade-off between the approximation ratio and running time: in $n^{O(q)}$ time, we get an approximation within factor $O_d((n/q)^{d/2-1})$ for arbitrary polynomials, $O_d((n/q)^{d/4-1/2})$ for polynomials with non-negative coefficients, and $O_d(sqrt{m/q})$ for sparse polynomials with $m$ monomials. The approximation guarantees are with respect to the optimum of the level-$q$ sum-of-squares (SoS) SDP relaxation of the problem. Known polynomial time algorithms for this problem rely on decoupling lemmas. Such tools are not capable of offering a trade-off like our results as they blow up the number of variables by a factor equal to the degree. We develop new decoupling tools that are more efficient in the number of variables at the expense of less structure in the output polynomials. This enables us to harness the benefits of higher level SoS relaxations. We complement our algorithmic results with some polynomially large integrality gaps, albeit for a slightly weaker (but still very natural) relaxation. Toward this, we give a method to lift a level-$4$ solution matrix $M$ to a higher level solution, under a mild technical condition on $M$.

From Weak to Strong LP Gaps for all CSPs

We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by $Omegaleft(frac{log n}{log log n}right)$ levels of the Sherali-Adams hierarchy on instances of size $n$. It was proved by Chan et al. [FOCS 2013] that any polynomial size LP extended formulation is no stronger than relaxations obtained by a super-constant levels of the Sherali-Adams hierarchy.. Combining this with our result also implies that any polynomial size LP extended formulation is no stronger than the basic LP. Using our techniques, we also simplify and strengthen the result by Khot et al. [STOC 2014] on (strong) approximation resistance for LPs. They provided a necessary and sufficient condition under which $Omega(log log n)$ levels of the Sherali-Adams hierarchy cannot achieve an approximation better than a random assignment. We simplify their proof and strengthen the bound to $Omegaleft(frac{log n}{log log n}right)$ levels.