Hi all,
Tomorrow Hamoon Moussavi will tell us about 'Non-commutativity for combinatorial optimization'. See below for the abstract. The talk will take place at 2pm in HIT E 41.1.
Contrary to the past, there will be no zoom livestreaming anymore of the QIT seminar.
Best,
Ladina
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 story to other problems in combinatorial optimization. The hope here is to obtain better approximation ratios. 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?