The multiparty communication complexity of set disjointness (Q2817790)

The paper presents in great detail and with an extended bibliography an important and recent result in communication complexity theory, and many of its consequences. Any reader interested in knowing more about fundamental questions in communication complexity, or about the innovative technique used to obtain this result, called the pattern matrix method, will greatly benefit from reading this clear, well-organized and pedagogic paper.NEWLINENEWLINECommunication complexity theory studies the amount of data that needs to be exchanged between nodes to compute a function. It completely ignores space and time complexity, to focus on the cost of sending and receiving messages. This field of study was invented in the early 80s, impacted many aspects of theoretical computer science, and gave rise to many interesting problems and techniques. The disjointness problem (determining if all the nodes have a piece of data in common) in a multiparty communication environment (i.e., when more than 2 nodes are involved) is a relatively old, central and well-studied problem. This paper offers a new lower bound for particular instances of that problem, as well as a proof of the so-called ``direct product theorem'' that concerns the communication needed to solve multiple instances of that problem.NEWLINENEWLINEThis paper uses a technique invented by the author, called the the pattern matrix method. How it works, why it improves on previous results, and some of its applications, are explained in great detail, making the paper extremely enjoyable to read, as well as inspiring. It is a well-crafted paper, including numerous and detailed references to previous bounds and analyses of that problem, and technically solid and convincing.