The Taub Faculty of Computer Science Events and Talks

In 1979, Yao has defined the communication complexity model, including the two measures: Deterministic communication complexity and partition number. The relation between deterministic communication complexity and the partition number has been in the focus of much research in the field of communication complexity. Yao has noticed that the logarithm of the partition number is a lower bound on the deterministic communication complexity, and inquired about the exact relation. In 1991, Yannakakis has proven that the square of the logarithm of the partition number is, in fact, an upper bound on the deterministic communication complexity, and asked a question that remained open until 2015: Is the upper bound tight? An affirmative answer to the tightness question was established in 2015 by Goos, Pitassi and Watson. However, many other questions remained unanswered. In particular, given a specific function, where is its deterministic communication complexity on the spectrum between Yao's lower bound and Yannakakis' upper bound? As the best general lower bound technique is, in fact, Yao's lower bound, this question remains open. In our research we study a specific class of functions called "The clique vs. independent set" functions, which are two argument functions induced by simple graphs G, in which one party gets a clique in G, the other an independent set in G, and their goal is to determine whether their sets intersect or not. The class of clique vs. independent set functions attracted much research in the field of communication complexity as they are in some sense the computational complexity analogue of computationally hard problems. We prove that such functions, induced by quasi-random graphs have a non-trivial lower bound that separates from Yao's lower bound. We achieve the above by studying the behavior of the partition number measure through the process of protocol partition. NOTE: We assume no background in communication complexity.