We prove that it is NP-hard to approximate the non-commutative Grothendieck problem to within any constant factor larger than one-half, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of finite-dimensional Hilbert spaces into the space of matrices endowed with the trace norm with the property that the image of standard basis vectors is longer than that of unit vectors with no large coordinates.
We prove that it is NP-hard to approximate the non-commutative Grothendieck problem to within any constant factor larger than one-half, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of finite-dimensional Hilbert spaces into the space of matrices endowed with the trace norm with the property that the image of standard basis vectors is longer than that of unit vectors with no large coordinates.
The Grothendieck constant KG is the smallest constant such that for every d ∈ N and every matrix A = (aij), sup u i,v j ∈B (d) X aij〈ui, vj 〉 � KG · ij sup x i,y j ∈[−1,1] X ij aijxiyj, where B (d) is the unit ball in R d. Despite several efforts [15, 23], the value of the constant KG remains unknown. The Grothendieck constant KG is precisely the integrality gap of a natural SDP relaxation for the KM,N-Quadratic Programming problem. The input to this problem is a matrix A = (aij) and the objective is to maximize the quadratic form P ij aijxiyj over xi, yj ∈ [−1, 1]. In this work, we apply techniques from [22] to the KM,N-Quadratic Programming problem. Using some standard but non-trivial modifications, the reduction in [22] yields the following hardness result: Assuming the Unique Games Conjecture [9], it is NP-hard to approximate the KM,N-Quadratic Programming problem to any factor better than the Grothendieck constant KG. By adapting a “bootstrapping ” argument used in a proof of Grothendieck inequality [5], we are able to perform a tighter analysis than [22]. Through this careful analysis, we obtain the following new results: ◦ An approximation algorithm for KM,N-Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant KG (optimal approximation ratio assuming the Unique Games Conjecture). ◦ We show that the Grothendieck constant KG can be computed within an error η, in time depending only on η. Specifically, for each η, we formulate an explicit finite linear program, whose optimum is η-close to the Grothendieck constant. We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.
The Grothendieck constant KG is the smallest constant such that for every d ∊ ℕ and every matrix A = (aij), where B(d) is the unit ball in ℝd. Despite several efforts [15, 23], the value of the constant KG remains unknown. The Grothendieck constant KG is precisely the integrality gap of a natural SDP relaxation for the KM,N-Quadratic Programming problem. The input to this problem is a matrix A = (αij) and the objective is to maximize the quadratic form Σij aijxiyj over xi, yj ∊ [–1, 1]. In this work, we apply techniques from [22] to the KM,N-Quadratic Programming problem. Using some standard but non-trivial modifications, the reduction in [22] yields the following hardness result: Assuming the Unique Games Conjecture [9], it is NP-hard to approximate the KM,N-Quadratic Programming problem to any factor better than the Grothendieck constant KG. By adapting a “bootstrapping” argument used in a proof of Grothendieck inequality [5], we are able to perform a tighter analysis than [22]. Through this careful analysis, we obtain the following new results: An approximation algorithm for KM,N-Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant KG (optimal approximation ratio assuming the Unique Games Conjecture). We show that the Grothendieck constant KG can be computed within an error η, in time depending only on η. Specifically, for each η, we formulate an explicit finite linear program, whose optimum is η-close to the Grothendieck constant. We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.
Semidefinite relaxations are a powerful tool for approximately solving combinatorial optimization problems such as MAX-CUT and the Grothendieck problem. By exploiting a bounded rank property of extreme points in the semidefinite cone, we make a sub-constant improvement in the approximation ratio of one such problem. Precisely, we describe a polynomial-time algorithm for the positive semidefinite Grothendieck problem -- based on rounding from the standard relaxation -- that achieves a ratio of 2/π+Θ(1/n), whereas the previous best is 2/π+Θ(1/n). We further show a corresponding integrality gap of 2/π+O~(1/n1/3).
We prove the following about the Nearest Lattice Vector Problem (in any l/sub p/ norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some /spl epsiv/>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2/sup log(0.5-/spl epsiv/)/ /sup n/ then NP is in quasi-polynomial deterministic time: NP/spl sube/DTIME(n/sup poly(log/ /sup n)/). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l/sub /spl infin// norm. Improving the factor 2/sup log(0.5-/spl epsiv/)/ /sup n/ to /spl radic/(dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l/sub 2/ norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem.>
The little Grothendieck problem (a special case of Boolean quadratic optimization) consists of maximizing P ij Cijxixj over binary variables xi 2 f 1g, where C is a positive semidenite matrix. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given C 2 R dn dn a positive semidenite matrix, the objective is to maximize P ij tr C T ijOiO T restricting Oi to take values in the group of orthogonal matrices O(d), where Cij denotes the (ij)-th d d block of C. We propose an approximation algorithm, to which we refer as Orthogonal-Cut, to solve the little Grothendieck problem over the group of orthogonal matrices O(d) and show a constant approximation ratio. Our method is based on semidenite programming where the relaxation is inspired by the work of Goemans and Williamson in the context of the MaxCut problem. For a given d 1, we show a constant approximation ratio of 2, where d is the expected average singular value of a d d matrix with random GaussianN 0; 1 i.i.d. entries. For d = 1 we recover the known 2 = 2= approximation guarantee for the classical little Grothendieck problem. Orthogonal-Cut also serves as an approximation algorithm for several applications including the Procrustes problem where it improves over the best previously known approximation ratio of 1 2 p 2 . The little Grothendieck problem falls under the larger class of problems approximated by an algorithm recently proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and gives a better approximation ratio.