Classical Pseudo-Telepathy
Previous results:
-
- The Pseudo-Telepathy Game is analogue to the ‚restricted equality problem‘ in [Buhrman, Cleve, Widgerson, 1998]. They proved by using [Frank, Rodl, 1987] that problem has a deterministic communication complexity of . Therefore we need classical bits to win.