M.Sc Thesis

M.Sc StudentZehavi Sa'ar
SubjectOn the Gap Between Deterministic Communication Complexity
and the Partition Number
DepartmentDepartment of Computer Science
Supervisor PROF. Eyal Kushilevitz
Full Thesis textFull thesis text - English Version


Two central complexity measures in the field of communication complexity are χ1(f) and Dcc(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, Dcc(f)O(log22 χ1(f)). It was conjectured that this bound is tight. Namely, that there exists a function f, such that Dcc(f) ≥ Ω? (log22 χ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(χ1(f)) versus the Dcc(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 > 1, such that Dcc(f) ≥ clog21(f)). In effort to better understand the nature of these functions, we find a property we call quasirandomness, such that functions that possess this property satisfy: Dcc(f) ≥ log(χ1(f))???(χ1(f)). This problem seems to be difficult, as there are no known general techniques that allow one to prove a lower bound on Dcc(f) that separates it from log21(f)).