Chennai Mathematical Institute


12:00 - 1:00 pm,Seminar Hall
Connecting query and communication algorithms:Upper and lower bounds

Sagnik Mukhopadhyay
KTH Royal Institute of Technology, Sweden.


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.

- I will present a generalized simulation theorem by singling out a new pseudo-random property of a function g, that we call "having (delta; h)-hitting rectangle distributions", and then showing that a simulation theorem will hold for any g with this property, i.e., the communication complexity of f o g will be lower bounded by the query complexity of f times the communication complexity of g. Moreover, I will point out that two well- studied functions---the inner-product function and the gap-Hamming family of functions---have the above property in addition to the indexing function. This is joint work with Arkadev Chattopadhyay, Michal koucky and Bruno Loff (CC 2019).

- Towards showing sufficiency of such a theorem, I will show that (1) when g = Equality it does not admit a hitting rectangle-distribution and also does not admit a simulation theorem as above, but (2) it does admit a simulation theorem where, instead of the query complexity of f, the measure of complexity of f that is of interest is the AND-query complexity of f. This is joint work with Bruno Loff (STACS 2019).

- In the asymmetric setting where the input is not distributed equally between processors, I will show a simulation theorem where we connect the asymmetric communication complexity of f o g to the parity decision tree of f. As applications, I will mention (1) a strong data-structure lower bound for vector-matrix-vector problem in F2, and (2) a lower bound provably better than what can be obtained by classical richness technique of Miltersen et al. This is a joint work with Arkadev Chattopadhyay, Michal koucky and Bruno Loff (STOC 2018).

- On the other direction, I will mention an interesting query algorithm for a celebrated submodular function minimization problem on graph, namely the weighted min-cut problem. I will also mention how this algorithm acts as an inspiration to come up with a tight communication protocol for the same problem. I will present the details of these algorithms in a later talk. This is a joint work with Danupon Nanongkai (under submission).

I will conclude the talk by presenting some interesting open directions for future research.