Characterization of Rigid Magic Binary Constraint Games on Graphs
Two player binary constraint games are games where Alice and Bob are asked to assign 0 and 1 to variables subject to some constraints. The magic pentagram game and magic square game are two such games with unique quantum strategies that win with probability 1 (while classical strategies succeed with probability less than 1). For a class of games that generalizes the magic square and pentagram, we show that any game with a unique strategy is basically equivalent to either the magic square or magic pentagram. We provide a graph theoretic characterization of these games. (Joint work with Amir Kalev and Carl Miller)
Note: There will be snacks and drinks at 4:00pm and the talk is from 4:10pm to 4:40pm.