RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

Characterization of Rigid Magic Binary Constraint Games on Graphs

April 6, 2018 - 4:00pm
Speaker: 
Aaron Ostrander
Institution: 
QuICS

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.

PSC 2136