Computer Science Thesis Oral

Wednesday, June 19, 2019 - 9:30am to 11:00am


Traffic21 Classroom 6501 Gates Hillman Centers



On the Approximability of Injective Tensor for Norm

The theory of approximation algorithms has had great success with combinatorial optimization, where it is known that for a variety of problems, algorithms based on semidefinite programming are optimal under the unique games conjecture. In contrast, the approximability of most continuous optimization problems remains unresolved. 

In this thesis we aim to extend the theory of approximation algorithms to a wide class of continuous optimization problems, namely those captured by the injective tensor norm. Given an order-d tensor T, and symmetric convex sets C1, ... Cd, the injective tensor norm of T is defined as sup_{xi in Ci} <T,x1 otimes ... otimes xd>.

Injective tensor norm has manifestations across several branches of computer science, optimization and analysis. To list some examples, it has connections to maximum singular value, max-cut, Grothendieck's inequality, non-commutative Grothendieck inequality, quantum information theory, k-XOR, refuting random constraint satisfaction problems, tensor PCA, densest-k-subgraph, and small set expansion. So a general theory of its approximability promises to be of broad scope and applicability.

We study various important special cases of the problem (through the lens of convex optimization and the sum of squares (SoS) hierarchy) and obtain the following results:

  — We obtain the first NP-hardness of approximation results for hypercontractive norms. Specifically, we prove inapproximability results for computing the p->q operator norm when p<= q and 2 is not in [p,q].

Towards the goal of obtaining strong inapproximability results for 2->q norm when q>2, we give random label cover based hardness results for mixed norms, i.e. 2 -> l_q(l_q') for some 2<q,q'<infinity.

  — We obtain improved approximation algorithms for computing the p->q operator norm when p>= 2>= q.    

  — We introduce the technique of weak decoupling inequalities and use it to analyze the integrality gap of the SoS hierarchy for the maxima of various classes of polynomials over the sphere, namely arbitrary polynomials, polynomials with non-negative coefficients and sparse polynomials. We believe this technique is broadly applicable and could find use beyond optimization over the sphere.

  — We also study how well higher levels of SoS approximate the maximum of a random polynomial over the sphere.

Thesis Committee:
Venkatesan Guruswami (Chair)
Anupam Gupta
David Woodruff
Madhur Tulsiani (Toyota Technological Institute Chicago)

For More Information, Contact:


Thesis Oral