#### Alladi Ramakrishnan Hall

#### Connecting query and communication algorithms: Upper and lower bounds

#### Sagnik Mukhopadhyay

##### KTH, Stockholm

*I will present recent advancements in communication protocols and*

query algorithms. These two models of computations are extremely versatile---

both from the perspective of complexity theory and that of designing

algorithms with sub-linear complexity. We are interested in investigating the

connection between these two complexity measures. One particular interest in

recent times is proving communication lower bound for composed functions of

the form f o g in terms of some complexity measure of f and the communication

complexity of g. Such theorem is known as `simulation/lifting theorem'. I will

present a few results in this direction.

Done