Abstract: The communication complexity of a function f(x,y) is the number of bits that Alice and Bob need to communicate in order to compute f, when Alice has x and Bob has y. It is a long-held belief that this quantity, which we gave an operational definition of, should be closely related to the rank of the communication matrix of f.
In our recent work, "The Log-Approximate-Rank Conjecture is False", we show that randomized communication and approximate rank do not have the close relationship that we would have liked to believe, thus refuting the titular conjecture.
In this talk, we will discuss why communication and rank are believed to be related. We will also see that our counter-example actually stems from a poor understanding of the model of parity decision trees, leaving us with fundamental open problems even in such simple models of computation (joint work with Arkadev Chattopadhyay and Nikhil Mande).
