Partition Arguments In Communication Complexity

Joint work with Eyal Kushilevitz

Enav Weinreb, CWI Amsterdam

Consider the "plain" multiparty communication complexity model, where k players P1 , ... , Pk holding inputs x1 , ... , xk in {0,1}n (respectively) communicate in order to compute the value f ( x1 , ... , xk ). The main lower bound technique for such communication problems is that of partition arguments: partition the k-players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem. In this paper, we study the power of the partition arguments method in different communication complexity models: the deterministic, the non-deterministic and the randomized models of communication.

back to EIDMA Seminar Combinatorial Theory announcements