Technical Report MSC-2018-19

Title: On the Gap Between Deterministic Communication Complexity and the Partition Number
Authors: Sa'ar Zehavi
Supervisors: Eyal Kushilevitz
PDFCurrently accessibly only within the Technion network
Abstract: Two central complexity measures in the field of communication complexity are $\chi_1(f)$ and $D^{cc}(f)$, which denote the so-called partition number and the deterministic communication complexity of a function $f$, respectively. The relation between these two complexity measures has been the focus of much research. In 1992, in a work that focused on refuting a possible proof strategy for the $P$ versus $NP$ problem, Yannakakis has shown that for all functions $f$, the deterministic communication complexity of $f$ is upper bounded as a function of the partition number, specifically, $D^{cc}(f) \le O(\log_2^2(\chi_1(f)))$. It was conjectured that this bound is tight. Namely, that there exists a function $f$, such that $D^{cc}(f) \ge \tilde{\Omega}(\log_2^2(\chi_1(f)))$, where the tilde notation hides poly-logarithmic factors. In 2015, Göös, Pitassi and Watson proved that the bound is tight. Their construction, although shedding light on the problem, namely, rectifying the conjecture about the tightness of the upper bound, has left many questions regarding the nature of such functions open. Two such questions which we handle within this thesis are as follows. First, in the realm of communication complexity there is a special class of functions, induced by graphs, called the clique versus independent set functions, denoted $CLIS$. $CLIS$ functions are considered interesting as they form a notion of hard -problems with respect to the $\log(\chi_1(f))$ versus the $D^{cc}(f)$ gap. As the existence of a quadratic gap-exhibiting function can be phrased in terms of the existence of a quadratic gap exhibiting $CLIS$ function, the search space for such gap-exhibiting functions shrinks to the space of $CLIS$ problems. As the known construction of a graph, with a quadratic gap-exhibiting $CLIS$ function is implicit, we ask whether its implicitness is an inherent property of such a construction. I.e. we ask whether, similar to other examples of nonconstructive combinatorial proofs, such as the existence of Ramsey graphs, for which there are known proofs of existence, yet no known explicit constructions. If true, this may give some insight as to why this problem was open for so many years. If false, this may give hope to the existence of more direct proofs. We answer this question negatively in Chapter 3 by turning the construction of the underlying graph in Göös et al's $CLIS$ function explicit . Second, Göös et al.'s construction, although giving an example of a gap-exhibiting function, does not encompass tools for deciding whether a given function exhibits a quadratic gap between its deterministic communication complexity and the logarithm of its partition number, or even for deciding whether a given function exhibits a constant gap, i.e., that there exists $c \ge 1$, such that $D^{cc}(f) \ge c\log_2(\chi_1(f))$. In effort to better understand the nature of these functions, we define a property we call quasirandomness, such that functions that possess this property satisfy: $D^{cc}(f) \ge \log(\chi_1(f))+1/2\log\log(\chi_1(f)))$. This problem seems to be difficult, as there are no known general techniques that allow one to prove a lower bound on $D^{cc}(f)$ that separates it from $\log_2(\chi_1(f))$.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2018
To the main CS technical reports page

Computer science department, Technion