Discrete Mathematics and Optimization Seminar

---

ANNE BROADBENT
Universite de Montreal
Monday November 26th at 4.30pm
Burnside 1205



Title. Bipartite Games and Winning Strategies

Abstract. We study bipartite games that arise in the context of nonlocality with the help of graph theory. Our main
results are that deciding whether a no-communication classical winning strategy exists for certain games
(called forbidden-edge and covering games) is NP-complete, while the problem of deciding if these games
admit a non-signalling winning strategy is in P. We also show that every pseudo-telepathy game yields both
a proof of the Bell-Kochen-Specker theorem and an instance of a two-prover interactive proof that is
classically sound, but that becomes unsound when provers use shared entanglement.