Abstract

In the communication complexity model, Alice and Bob are given some inputs and they jointly try to compute some function on this inputs via communicating over a channel (which could be classical or quantum). The goal is to minimize the amount of communication needed to solve this problem. On the other hand, a non local box is a device that allows two players to win the CHSH game with probability one but does not allow them to communicate with each other. In this talk we will consider the following questions: What happens if instead of a communication channel Alice and Bob share non-local boxes but cannot communicate at all? Is it still possible for them to jointly solve the problem? What is the relation between the amount of communication and the number of non local boxes needed? We will define the model of non-local box complexity and provide some interesting relations to the classical and quantum communication complexity model.