Towards computing the Grothendieck constant

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Towards computing the Grothendieck constant

Full text

Pdf (532 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms table of contents

New York, New York

Pages 525-534

Year of Publication: 2009

Authors

Prasad Raghavendra	University of Washington, Seattle, WA
David Steurer	Princeton University, Princeton, NJ

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 71, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

The Grothendieck constant K_G is the smallest constant such that for every d ∈ N and every matrix A = (a_ij),

[EQUATION]

where B^(d) is the unit ball in R^d. Despite several efforts [15, 23], the value of the constant K_G remains unknown. The Grothendieck constant K_G is precisely the integrality gap of a natural SDP relaxation for the K_{M, N}-Quadratic Programming problem. The input to this problem is a matrix A = (a_ij) and the objective is to maximize the quadratic form Σ_ij a_ijx_iy_j over x_iy_j ∈ [−1, 1].

In this work, we apply techniques from [22] to the K_{M, 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 K_{M, N}-Quadratic Programming problem to any factor better than the Grothendieck constant K_G.

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 K_{M, N}-Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant K_G (optimal approximation ratio assuming the Unique Games Conjecture).

• We show that the Grothendieck constant K_G 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Noga Alon , Konstantin Makarychev , Yury Makarychev , Assaf Naor, Quadratic forms on graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060664]
	2	Noga Alon , Assaf Naor, Approximating the Cut-Norm via Grothendieck's Inequality, SIAM Journal on Computing, v.35 n.4, p.787-803, 2006 [doi>10.1137/S0097539704441629]
	3	Sanjeev Arora , Eli Berger , Elad Hazan , Guy Kindler , Muli Safra, On Non-Approximability for Quadratic Programs, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.206-215, October 23-25, 2005 [doi>10.1109/SFCS.2005.57]
	4	Amin Coja-Oghlan , Colin Cooper , Alan Frieze, An efficient sparse regularity concept, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.207-216, January 04-06, 2009, New York, New York
	5	B. W. Johnson and J. Lindenstrauss. Basic concepts in the geometry of Banach spaces. Handbook of the geometry of Banach spaces, North Holland, Amsterdam, 1:1--84, 2001.
	6	Moses Charikar , Anthony Wirth, Maximizing Quadratic Programs: Extending Grothendieck's Inequality, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.54-60, October 17-19, 2004 [doi>10.1109/FOCS.2004.39]
	7	A. Frieze and R. Kannan. Quick approximation to matrices and applications. Combinatorica, 19(2):175--220, 1999.
	8	A. Grothendieck. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat, 8:1--79, 1953.
	9	Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
	10	Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O’Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, SIAM Journal on Computing, v.37 n.1, p.319-357, April 2007 [doi>10.1137/S0097539705447372]
	11	Subhash Khot , Ryan O'Donnell, SDP gaps and UGC-hardness for MAXCUTGAIN, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.217-226, October 21-24, 2006 [doi>10.1109/FOCS.2006.67]
	12	Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
	13	Guy Kindler , Assaf Naor , Gideon Schechtman, The UGC hardness threshold of the ℓ_p Grothendieck problem, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.64-73, January 20-22, 2008, San Francisco, California
	14	H. König. Spherical functions and the Grothendieck inequality. Unpublished manuscript, 2005. Available at http://shrimp.bayou.uni-linz.ac.at/Vienna2005/pdf/koenig.pdf.
	15	J. L. Krivine. Constantes de Grothendieck et fonctions de type positif sur les sphères. Adv. Math., 31:16--30, 1977--1978.
	16	J. Lindenstrauss and A. Pelczyński. Absolutely summing operators in L_p spaces and their applications. Studia Math, 29:275--326, 1968.
	17	Nati Linial , Adi Shraibman, Lower bounds in communication complexity based on factorization norms, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250892]
	18	A. Megretski. Relaxation of quadratic programming in operator theory and systems analysis. Systems, approximation, singular integral operators and related topics, 2001.
	19	Elchanan Mossel, Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.156-165, October 25-28, 2008 [doi>10.1109/FOCS.2008.44]
	20	E. Mossel, R. O'Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. To appear in Ann. Math., 2008.
	21	A. Nemirovski, C. Roos, and T. Terlaky. On maximization of quadratic form over intersection of ellipsoids with common center. Mathematical Programming, 86(3):463--473, 1999.
	22	Prasad Raghavendra, Optimal algorithms and inapproximability results for every CSP?, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374414]
	23	J. Reeds. A new lower bound on the real Grothendieck constant. Unpublished Manuscript, 1993. Available at http://www.dtc.umn.edu/~reedsj.