On Query and Communication Complexity

In the first part, we will consider the connection between two well-known complexity measures --- communication complexity and query complexity. For a composed function $f \circ g$, where $f: \{0,1\}^p \rightarrow \mathcal{Z}$ and $g : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$, we will show a sufficient condition for $g$ such that the communication complexity of $f \circ g$ becomes tightly bounded by the query complexity of $f$ times the communication complexity of $g$. Such a theorem is known as simulation theorem or lifting theorem in literature. We will also show two well-known functions for which the said condition holds. This part deals with deterministic complexity measures.

In the second part of the talk, we will deal with randomized complexity measure. We consider a specific composed function $\text{elim} \circ g$, namely the elimination function, and we will demonstrate a key property of $g$, namely the regularity property, which is closely related to the communication complexity of the elimination problem. To this end, we will show a tight connection between regularity and another well-studied pseudo-random property of $g$, namely, discrepancy.

In the third part, we will get into the realm of asymmetric communication complexity where one of the players holds an input of considerably smaller length than that of the other player. We will show two results here --- (a) We will consider function like $g^p$ and show direct-sum results for such functions in asymmetric setting, and (b) we will show tight randomized lower bound for a composed function, namely, the asymmetric unordered search function. We will allude to the role of regularity in obtaining such a lower bound.

In the last part of the talk, we will talk about communication complexity in multiparty number-in-hand coordinator model. We will show a tight lower bound for a well-studied function (in two-party model), namely the tribes function, in this setting.