Bypassing UGC From Some Optimal Geometric Inapproximability Results

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In our work we bypass the UGC assumption in inapproximability results for two geometric problems, obtaining a tight NP-hardness result in each case. This talk shall focus on one of the problems as described below.

The problem we consider is the L_p Quadratic Grothendieck Maximization Problem, considered by Kindler, Naor and Schechtman. Here, the input is a multilinear quadratic form and the goal is to maximize the quadratic form over the ell_p unit ball. The problem is polytime solvable for p=2. We show that for any finite constant p > 2, it is NP-hard to approximate the quadratic form to within a factor of gamma_p^2 - eps for any eps > 0, where gamma_p is the pth moment of a standard gaussian. The same hardness factor was earlier shown under the UGC by Kindler et al. We also obtain a gamma_p^2-approximation algorithm for the problem using a convex relaxation of the problem.

Based on joint work with Venkatesan Guruswami, Prasad Raghavendra and Yi Wu.