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.