Tight Hardness of the Non-Commutative Grothendieck Problem

by Jop Briët, Oded Regev, and Rishi Saket

Theory of Computing, Volume 13(15), pp. 1-24, 2017

Bibliography with links to cited articles

[1]   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]

[2]   Afonso S. Bandeira, Christopher Kennedy, and Amit Singer: Approximating the little Grothendieck problem over the orthogonal group. Math. Program., 160(1-2):433–475, 2016. [doi:10.1007/s10107-016-0993-7, arXiv:1308.5207]

[3]   Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou: Hypercontractivity, sum-of-squares proofs, and their applications. In Proc. 44th STOC, pp. 307–326. ACM Press, 2012. [doi:10.1145/2213977.2214006, arXiv:1205.4484]

[4]   Vidmantas Bentkus: A Lyapunov type bound in Rd. Theory Probab. Appl., 49(2):311–323, 2005. Translated from Russian. [doi:10.1137/S0040585X97981123]

[5]   Stéphane Boucheron, Gábor Lugosi, and Pascal Massart: Concentration Inequalities. Oxford Univ. Press, 2013.

[6]   Mark Braverman, Konstantin Makarychev, Yury Makarychev, and Assaf Naor: The Grothendieck constant is strictly smaller than Krivine’s bound. Forum Math. Pi, 1:e4, 42, 2013. Preliminary version in FOCS’11. [doi:10.1017/fmp.2013.4]

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

[8]   Jop Briët, Oded Regev, and Rishi Saket: Tight hardness of the non-commutative Grothendieck problem. In Proc. 56th FOCS, pp. 1108–1122. IEEE Comp. Soc. Press, 2015. [doi:10.1109/FOCS.2015.72]

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

[10]   Uriel Feige and Gideon Schechtman: On the optimality of the random hyperplane rounding technique for MAX CUT. Random Structures Algorithms, 20(3):403–440, 2002. [doi:10.1002/rsa.10036]

[11]   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 from Instituto de Matemática e Estatística da Universidade de São Paulo.

[12]   Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, and Yi Wu: Bypassing UGC from some optimal geometric inapproximability results. ACM Trans. Algor., 12(1):6:1–6:25, 2016. Preliminary version in SODA’12. [doi:10.1145/2737729]

[13]   Uffe Haagerup: The Grothendieck inequality for bilinear forms on C*-algebras. Adv. in Math., 56(2):93 – 116, 1985. [doi:10.1016/0001-8708(85)90026-X]

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

[15]   Uffe Haagerup and Takashi Itoh: Grothendieck type norms for bilinear forms on C*-algebras. J. Operator Theory, 34(2):263–283, 1995. Available from JSTOR.

[16]   Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]

[17]   Wassily Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58(301):13–30, 1963. [doi:10.1007/978-1-4612-0865-5_26]

[18]   Roger A. Horn and Charles R. Johnson: Matrix Analysis. Cambridge Univ. Press, 1990.

[19]   Subhash Khot: Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Proc. 43rd FOCS, pp. 23–32. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181879]

[20]   Subhash Khot: On the unique games conjecture. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 99–121. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.19]

[21]   Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447372]

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

[23]   Subhash Khot and Assaf Naor: Grothendieck-type inequalities in combinatorial optimization. Comm. Pure Appl. Math., 65(7):992–1035, 2012. [doi:10.1002/cpa.21398, arXiv:1108.2464]

[24]   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]

[25]   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]

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

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

[28]   Assaf Naor, Oded Regev, and Thomas Vidick: Efficient rounding for the noncommutative Grothendieck inequality. Theory of Computing, 10(11):257–295, 2014. Preliminary version in STOC’13. [doi:10.4086/toc.2014.v010a011]

[29]   Yurii Nesterov: Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Softw., 9(1-3):141–160, 1998. [doi:10.1080/10556789808805690]

[30]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014. Available at Semantic Scholar. [doi:10.1017/CBO9781139814782]

[31]   Gilles Pisier: Grothendieck’s theorem for noncommutative C*-algebras, with an appendix on Grothendieck’s constants. J. Funct. Anal., 29(3):397–415, 1978. [doi:10.1016/0022-1236(78)90038-1]

[32]   Gilles Pisier: Grothendieck’s theorem, past and present. Bull. Amer. Math. Soc., 49(2):237–323, 2012. [doi:10.1090/S0273-0979-2011-01348-9, arXiv:1101.4195]

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

[34]   Oded Regev and Thomas Vidick: Quantum XOR games. ACM Trans. Comput. Theory, 7(4):15:1–15:43, 2015. Preliminary version in CCC’13. [doi:10.1145/2799560, arXiv:1207.4939]

[35]   Ronald E. Rietz: A proof of the Grothendieck inequality. Israel J. Math., 19(3):271–276, 1974. [doi:10.1007/BF02757725]

[36]   Luca Trevisan: On Khot’s unique games conjecture. Bull. Amer. Math. Soc. (N.S.), 49(1):91–111, 2012. [doi:10.1090/S0273-0979-2011-01361-1]

[37]   Boris S. Tsirel’son: Quantum analogues of the Bell inequalities. The case of two spatially separated domains. J. Soviet Math., 36(4):557–570, 1987. [doi:10.1007/BF01663472]