Grothendieck Inequalities for Semidefinite Programs with Rank Constraint

by Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin

Theory of Computing, Volume 10(4), pp. 77-105, 2014

Bibliography with links to cited articles

[1]   PARI/GP computer algebra system, version 2.5.3, Bordeaux, 2012. PARI/GP.

[2]   Milton Abramowitz and Irene Ann Stegun: Handbook of mathematical functions with formulas, graphs, and mathematical tables. U.S. Department of Commerce, National Bureau of Standards, 1964. Available at Internet Archive.

[3]   Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor: Quadratic forms on graphs. Invent. Math., 163(3):499–522, 2006. Preliminary version in STOC’05. [doi:10.1007/s00222-005-0465-9]

[4]   Noga Alon and Assaf Naor: Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput., 35(4):787–803, 2006. Preliminary version in STOC’04. [doi:10.1137/S0097539704441629]

[5]   George E. Andrews, Richard Askey, and Ranjan Roy: Special Functions. Volume 71 of Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, 1999. [doi:10.1017/CBO9781107325937]

[6]   Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra: On non-approximability for quadratic programs. In Proc. 46th FOCS, pp. 206–215. IEEE Comp. Soc. Press, 2005. See also at ECCC. [doi:10.1109/SFCS.2005.57]

[7]   Alain Aspect, Philippe Grangier, and Gérard Roger: Experimental tests of realistic local theories via Bell’s theorem. Phys. Rev. Lett., 47(7):460–463, 1981. [doi:10.1103/PhysRevLett.47.460]

[8]   John S. Bell: On the Einstein-Podolsky-Rosen paradox. Physics, 1(3):195–200, 1964. Available at Wissenschaftstheorie und Wissenschaftsgeschichte.

[9]   Aharon Ben-Tal and Arkadi Nemirovski: On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty. SIAM J. on Optim., 12(3):811–833, 2002. [doi:10.1137/S1052623400374756]

[10]   Mark Braverman, Konstantin Makarychev, Yury Makarychev, and Assaf Naor: The Grothendieck constant is strictly smaller than Krivine’s bound. In Proc. 52nd FOCS, pp. 453–462. IEEE Comp. Soc. Press, 2011. See also at arXiv. [doi:10.1109/FOCS.2011.77]

[11]   Jop Briët, Harry Buhrman, and Ben Toner: A generalized Grothendieck inequality and nonlocal correlations that require high entanglement. Comm. Math. Phys., 305(3):827–843, 2011. [doi:10.1007/s00220-011-1280-3]

[12]   Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin: The positive semidefinite Grothendieck problem with rank constraint. In Proc. 37th Internat. Colloq. on Automata, Languages and Programming (ICALP’10), pp. 31–42. Springer, 2010. [doi:10.1007/978-3-642-14165-2_4]

[13]   Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin: The Grothendieck problem with rank constraint. In Proceedings of the 19th Symposium on Mathematical Theory of Networks and Systems (MTNS’10), pp. 111–113, 2010. MTNS.

[14]   Moses Charikar and Anthony Wirth: Maximizing quadratic programs: Extending Grothendieck’s inequality. In Proc. 45th FOCS, pp. 54–60. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.39]

[15]   Richard Cleve, Peter Hřyer, Benjamin Toner, and John Watrous: Consequences and limits of nonlocal strategies. In Proc. 19th IEEE Conf. on Computational Complexity (CCC’04), pp. 236–249. IEEE Comp. Soc. Press, 2004. See also at arXiv. [doi:10.1109/CCC.2004.1313847]

[16]   Alexander Davie: Lower bound for KG. Unpublished, 1984.

[17]   Joe Diestel, Jan H. Fourie, and Johan Swart: The metric theory of tensor products: Grothendieck’s résumé revisited. Amer. Math. Soc., 2008. AMS.

[18]   Albert Einstein, Boris Podolsky, and Nathan Rosen: Can quantum-mechanical description of physical reality be considered complete? Physical Review, 47(10):777–780, 1935. [doi:10.1103/PhysRev.47.777]

[19]   Arthur Erdélyi, Wilhelm Magnus, Fritz Oberhettinger, and Francesco G. Tricomi: Tables of integral transforms, Vol. 1. McGraw-Hill, New York, 1954.

[20]   William Feller: An introduction to probability theory and applications. Volume II. John Wiley and Sons, New York, 1966.

[21]   David J. H. Garling: Inequalities: a journey into linear analysis. Cambridge Univ. Press, 2007. [doi:10.1017/CBO9780511755217]

[22]    Michel X. Goemans and David P. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, 1995. Preliminary version in STOC’94. [doi:10.1145/227683.227684]

[23]   Alexander Grothendieck: Résumé de la théorie métrique des produits tensoriels topologiques (French). Bol. Soc. Mat. Săo Paulo, 8:1–79, 1953. Available at Instituto de Matemática e Estatística da Universidade de Săo Paulo.

[24]   Uffe Haagerup: A new upper bound for the complex Grothendieck constant. Israel Journal of Mathematics, 60(2):199–224, 1987. [doi:10.1007/BF02790792]

[25]   Adolf Hurwitz: Vorlesungen über allgemeine Funktionentheorie und elliptische Funktionen. Spring, 1925. Available at Göttinger Digitalisierungszentrum.

[26]   Graham J. O. Jameson: Summing and nuclear norms in Banach space theory. Cambridge Univ. Press, 1987. [doi:10.1017/CBO9780511569166]

[27]   Subhash Khot and Assaf Naor: Linear equations modulo 2 and the L1 diameter of convex bodies. SIAM J. Comput., 38(4):1448–1463, 2008. Preliminary version in FOCS’07. [doi:10.1137/070691140]

[28]   Subhash Khot and Assaf Naor: Approximate kernel clustering. Mathematika, 55(1-2):129–165, 2009. Preliminary version in FOCS’08. [doi:10.1112/S002557930000098X]

[29]   Subhash Khot and Assaf Naor: Sharp kernel clustering algorithms and their associated Grothendieck inequalities. Random Structures & Algorithms, 42(3):269–300, 2013. Preliminary version in SODA’10. See also at arXiv. [doi:10.1002/rsa.20398]

[30]   Subhash Khot and Ryan O’Donnell: SDP gaps and UGC-hardness for Max-Cut-Gain. Theory of Computing, 5(4):83–117, 2009. Preliminary version in FOCS’06. [doi:10.4086/toc.2009.v005a004]

[31]   Guy Kindler, Assaf Naor, and Gideon Schechtman: The UGC hardness threshold of the Lp Grothendieck problem. Math. Oper. Res., 35(2):267–283, 2010. Preliminary version in SODA’08. [doi:10.1287/moor.1090.0425]

[32]   Hermann König: On an extremal problem originating in questions of unconditional convergence. In W. Haussmann, K. Jetter, and M. Reimer, editors, Recent Progress in Multivariate Approximation: 4th Internat. Conf., Witten-Bommerholz (Germany), Sep. 2000, volume 137 of Internat. Ser. Numer. Math., pp. 185–192. Birkhäuser, 2001. [doi:10.1007/978-3-0348-8272-9_14]

[33]   Jean-Louis Krivine: Constantes de Grothendieck et fonctions de type positif sur les sphčres. Advances in Math., 31(1):16–30, 1979. [doi:10.1016/0001-8708(79)90017-3]

[34]   Joram Lindenstrauss and Aleksander Pełczyński: Absolutely summing operators in Lp-spaces and their applications. Studia Math., 29(3):275–326, 1968. Available at EuDML.

[35]   Nati Linial and Adi Shraibman: Lower bounds in communication complexity based on factorization norms. Random Structures & Algorithms, 34(3):368–394, 2009. Preliminary version in STOC’07. [doi:10.1002/rsa.20232]

[36]   László Lovász: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(1):1–7, 1979. [doi:10.1109/TIT.1979.1055985]

[37]   Alexandre Megretski: Relaxations of quadratic programs in operator theory and system analysis. In Systems, Approximation, Singular Integral Operators, and Related Topics: International Workshop on Operator Theory and Applications (IWOTA’00), volume 129, pp. 365–392. Birkhäuser Basel, 2001. [doi:10.1007/978-3-0348-8362-7_15]

[38]   Assaf Naor and Oded Regev: Krivine schemes are optimal. Technical report, 2012. To appear in Proc. AMS. [arXiv:1205.6415]

[39]   Arkadi Nemirovski, Cornelis Roos, and Tamás Terlaky: On maximization of quadratic form over intersection of ellipsoids with common center. Mathematical Programming, 86(3):463–473, 1999. [doi:10.1007/s101070050100]

[40]   Yurii Nesterov: Semidefinite relaxations and nonconvex quadratic optimization. Optimization Methods and Software, 9(1-3):141–160, 1998. [doi:10.1080/10556789808805690]

[41]   Gilles Pisier: Factorization of linear operators and geometry of Banach spaces. Number 60 in CBMS regional conference series. Amer. Math. Soc., Providence, Rhode Island, 1986.

[42]   Prasad Raghavendra and David Steurer: Towards computing the Grothendieck constant. In Proc. 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’09), pp. 525–534. ACM Press, 2009. [ACM:1496770.1496828]

[43]   James Reeds: A new lower bound on the real Grothendieck constant. Available at author’s home page, 1991.

[44]   Oded Regev and Ben Toner: Simulating quantum correlations with finite communication. SIAM J. Comput., 39(4):1562–1580, 2009. Preliminary version in FOCS’07. [doi:10.1137/080723909]

[45]   Harry Eugene Stanley: Spherical model as the limit of infinite spin dimensionality. Physical Review, 176(2):718–722, 1968. [doi:10.1103/PhysRev.176.718]

[46]   Boris Tsirelson: Quantum analogues of the Bell inequalities. The case of two spatially separated domains. J. Soviet Math., 36:557–570, 1987. Translated from Problems of the Theory of Probability Distributions IX, Math. Inst. Steklov (LOMI), 142 (1985), pp. 174–194. (In Russian.) Available at author’s homepage.

[47]   Lieven Vandenberghe and Stephen Boyd: Semidefinite programming. SIAM Review, 38(1):49–95, 1996. [doi:10.1137/1038003]