Abstract
The celebrated Grothendieck's inequality is a fundamental result in Banach space theory that has recently found surprising applications in different areas, ranging from theoretical computer science (e.g. work of Alon and Naor showing how it could be used to derive a constant-factor approximation algorithm for the cut-norm), to quantum information theory (e.g. work of Tsirelson using it to derive upper bounds on the maximal violation of certain Bell inequalities by quantum mechanics).
In this talk I will briefly survey these results, before discussing a generalization of Grothendieck's inequality to non-commutative variables due to Pisier and Haagerup. I will motivate this inequality by showing that, just as its commutative counterpart, it leads to an efficient constant-factor approximation algorithm for a certain hard optimization problem. I will also describe a new application of the non-commutative Grothendieck's inequality to the computational complexity of quantum two-player games.
Based on joint work with Oded Regev.
Brief Biography
Thomas Vidick obtained his Ph.D. in Computer Science from UC Berkeley in Fall 2011, working with Umesh Vazirani. He is currently a postdoctoral researcher in MIT's CSAIL, working with Scott Aaronson. His research interests are in quantum computing and complexity theory, and he has made contributions to the theory of quantum multi-prover interactive proofs, quantum cryptography and pseudo-randomness.
