Tight Hardness of the Non-commutative Grothendieck Problem

DOI10.4086/toc.2017.v013a015zbMath1387.68122arXiv1412.4413OpenAlexW2787856857MaRDI QIDQ4602402

Jop Briët, Rishi Saket, Oded Regev

Publication date: 10 January 2018

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.4413

zbMATH Keywords

semidefinite programminghardness of approximationGrothendieck inequality

Mathematics Subject Classification ID

Semidefinite programming (90C22) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Functional analysis techniques applied to functions of several complex variables (32A70)

Related Items (7)

Failure of the trilinear operator space Grothendieck theorem ⋮ Approximating the little Grothendieck problem over the orthogonal and unitary groups ⋮ Moments of the Distance Between Independent Random Vectors ⋮ Unnamed Item ⋮ Survey on nonlocal games and operator space theory ⋮ Complexity and algorithms for finding a subset of vectors with the longest sum ⋮ Approximability of the Problem of Finding a Vector Subset with the Longest Sum

This page was built for publication: Tight Hardness of the Non-commutative Grothendieck Problem