Chattopadhyay, Mande and Sherif (to appear in STOC 2019) recently

exhibited a total Boolean function, the sink function, that has polynomial

approximate rank and polynomial randomized communication complexity. This gives

an exponential separation between randomized communication complexity and

logarithm of the approximate rank, refuting the log-approximate-rank conjecture.

We show that even the quantum communication complexity of the sink function is

polynomial, thus also refuting the quantum log-approximate-rank conjecture.

Our lower bound is based on the fooling distribution method introduced by Rao

and Sinha (Theory of Computing 2018) for the classical case and extended by

Anshu, Touchette, Yao and Yu (STOC 2017) for the quantum case. We also give a

new proof of the classical lower bound using the fooling distribution method.

Joint work with Ronald de Wolf.

exhibited a total Boolean function, the sink function, that has polynomial

approximate rank and polynomial randomized communication complexity. This gives

an exponential separation between randomized communication complexity and

logarithm of the approximate rank, refuting the log-approximate-rank conjecture.

We show that even the quantum communication complexity of the sink function is

polynomial, thus also refuting the quantum log-approximate-rank conjecture.

Our lower bound is based on the fooling distribution method introduced by Rao

and Sinha (Theory of Computing 2018) for the classical case and extended by

Anshu, Touchette, Yao and Yu (STOC 2017) for the quantum case. We also give a

new proof of the classical lower bound using the fooling distribution method.

Joint work with Ronald de Wolf.