12:00  1:00 pm,Seminar Hall Connecting query and communication algorithms:Upper and lower bounds Sagnik Mukhopadhyay KTH Royal Institute of Technology, Sweden. 230120 Abstract I will present recent advancements in communication protocols and query algorithms. These two models of computations are extremely versatileboth from the perspective of complexity theory and that of designing algorithms with sublinear 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 pseudorandom 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 functionsthe innerproduct function and the gapHamming family of functionshave 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 rectangledistribution 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 ANDquery 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 datastructure lower bound for vectormatrixvector 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 mincut 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.
