Speaker: |
Sagnik Mukhopadhyay |

Organiser: |
Vinod M. Prabhakaran |

Date: |
Thursday, 1 Jun 2017, 10:30 to 11:30 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

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.