Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM-SIAM Symposium on Discrete Algorithms (SODA)

Towards Computing the Grothendieck Constant

Prasad Raghavendra, David Steurer

Published Jan 4, 2009• 21 citations
Publisher

Abstract

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.

DOI
10.1137/1.9781611973068.58

Related papers

Towards computing the Grothendieck constant

Prasad Raghavendra, David Steurer

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.

Symposium on Discrete Algorithms•Jan 4, 2009•33 citations

On Non-Approximability for Quadratic Programs

Sanjeev Arora, Eli Berger, Guy Kindler +2 more

This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ that maximizes x/sup T/Mx. This problem recently attracted attention due to its application in various clustering settings, as well as an intriguing connection to the famous Grothendieck inequality. It is approximable to within a factor of O(log n), and known to be NP-hard to approximate within any factor better than 13/11 - /spl epsi/ for all /spl epsi/ > 0. We show that it is quasi-NP-hard to approximate to a factor better than O(log/sup /spl gamma// n)for some /spl gamma/ > 0. The integrality gap of the natural semidefinite relaxation for this problem is known as the Grothendieck constant of the complete graph, and known to be /spl Theta/(log n). The proof of this fact was nonconstructive, and did not yield an explicit problem instance where this integrality gap is achieved. Our techniques yield an explicit instance for which the integrality gap is /spl Omega/ (log n/log log n), essentially answering one of the open problems of Alon et al. [AMMN].

Annual Symposium on Foundations of Computer Science•Nov 15, 2005•75 citations

Approximating the Little Grothendieck Problem over the Orthogonal Group

Afonso S. Bandeira, Christopher Kennedy, Amit Singer

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.

•Aug 23, 2013•7 citations

Maximizing Quadratic Programs: Extending Grothendieck's Inequality

Moses Charikar, Anthony Ian Wirth

This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ such that x/sup T/Ax is maximized. Our approximation algorithm for this problem uses the canonical semidefinite relaxation and returns a solution whose ratio to the optimum is in /spl Omega/(1/ logn). This quadratic programming problem can be seen as an extension to that of maximizing x/sup T/Ay (where y's components are also /spl plusmn/1). Grothendieck's inequality states that the ratio of the optimum value of the latter problem to the optimum of its canonical semidefinite relaxation is bounded below by a constant. The study of this type of quadratic program arose from a desire to approximate the maximum correlation in correlation clustering. Nothing substantive was known about this problem; we present an /spl Omega/ (1/logn) approximation, based on our quadratic programming algorithm. We can also guarantee that our quadratic programming algorithm returns a solution to the MAXCUT problem that has a significant advantage over a random assignment.

Annual Symposium on Foundations of Computer Science•Dec 23, 2004•218 citations

Tight Hardness of the Non-commutative Grothendieck Problem

Jop Briot, Oded Regev, Rishi Saket

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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2015•9 citations

Tight Hardness of the Non-commutative Grothendieck Problem

Jop Briët, Oded Regev, Rishi Saket

$ \newcommand{\eps}{\varepsilon} $ We prove that for any $\eps > 0$ it is NP-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \eps$, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of $\ell_2$ 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 also observe that one can obtain a tight NP-hardness result for the commutative Little Grothendieck problem; previously, this was only known based on the Unique Games Conjecture (Khot and Naor, Mathematika 2009). A conference version of this paper appeared in the Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015).

arXiv:1412.4413•Theory of Computing•Jan 1, 2017•9 citations
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.
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.
This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ that maximizes x/sup T/Mx. This problem recently attracted attention due to its application in various clustering settings, as well as an intriguing connection to the famous Grothendieck inequality. It is approximable to within a factor of O(log n), and known to be NP-hard to approximate within any factor better than 13/11 - /spl epsi/ for all /spl epsi/ > 0. We show that it is quasi-NP-hard to approximate to a factor better than O(log/sup /spl gamma// n)for some /spl gamma/ > 0. The integrality gap of the natural semidefinite relaxation for this problem is known as the Grothendieck constant of the complete graph, and known to be /spl Theta/(log n). The proof of this fact was nonconstructive, and did not yield an explicit problem instance where this integrality gap is achieved. Our techniques yield an explicit instance for which the integrality gap is /spl Omega/ (log n/log log n), essentially answering one of the open problems of Alon et al. [AMMN].
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.
This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ such that x/sup T/Ax is maximized. Our approximation algorithm for this problem uses the canonical semidefinite relaxation and returns a solution whose ratio to the optimum is in /spl Omega/(1/ logn). This quadratic programming problem can be seen as an extension to that of maximizing x/sup T/Ay (where y's components are also /spl plusmn/1). Grothendieck's inequality states that the ratio of the optimum value of the latter problem to the optimum of its canonical semidefinite relaxation is bounded below by a constant. The study of this type of quadratic program arose from a desire to approximate the maximum correlation in correlation clustering. Nothing substantive was known about this problem; we present an /spl Omega/ (1/logn) approximation, based on our quadratic programming algorithm. We can also guarantee that our quadratic programming algorithm returns a solution to the MAXCUT problem that has a significant advantage over a random assignment.
$ \newcommand{\eps}{\varepsilon} $ We prove that for any $\eps > 0$ it is NP-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \eps$, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of ℓ2\ell_2ℓ2​ 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 also observe that one can obtain a tight NP-hardness result for the commutative Little Grothendieck problem; previously, this was only known based on the Unique Games Conjecture (Khot and Naor, Mathematika 2009). A conference version of this paper appeared in the Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015).