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]