Pseudo-Telepathy Games

Quantum information processing is a very interesting and important field which overlaps with physics, mathematics and informatics. It deals with harnessing laws and phenomena of the quantum world for computation. It especially studies what they enable us to do which goes beyond the abilities of classical information processing. Communication complexity of some distributed computational problems can be reduced with the help of quantum information processing. We speak of pseudo-telepathy when it is able to completely eliminate the need for communication. Such problems are often described using a terminology of the game theory and they are usually called pseudo-telepathy games. This thesis is intended to present, in a broader context, the main results of the author’s research in the area of pseudo-telepathy games. The following three main research directions may be distinguished. The thesis investigates important properties of several pseudo-telepathy games, studies the problem of playing pseudo-telepathy games in imperfect conditions and explores possible cryptographic applications of these games.