Extra QLunch: Hamoon Mousavi

Speaker: Hamoon Mousavi, Columbia University

Title: Non-commutativity for combinatorial optimization

Abstract: The Max-Cut problem is the meeting ground for two beautiful results in theoretical computer science: On the one hand we have the Tsirelson’s theorem for XOR games from quantum information and on the other hand we have the Goemans-Williamson’s hyperplane rounding algorithm, a celebrated result in combinatorial optimization. Making this connection explicit allows us to reinterpret the Goemans-Williamson algorithm in terms of operators rather than hyperplanes. We draw a few lessons from this reinterpretation and we see how one might extend this to other problems in combinatorial optimization. The hope here is to obtain better approximation ratios for combinatorial optimization problems. We also see how one can tell this story purely in terms of non-local games. In the language of non-local games the question we are trying to answer is: Is there a good classical strategy hidden somewhere inside every quantum strategy of a nonlocal game?