Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-204 | 30th November 2018 00:16

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank



Chattopadhyay, Mande and Sherif (ECCC 2018) 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 (ECCC 2015) 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.


Comment #1 to TR18-204 | 2nd December 2018 14:18

Independent Work

Authors: Makrand Sinha, Ronald de Wolf
Accepted on: 2nd December 2018 14:18


The same lower bound has been obtained independently and simultaneously by Anurag Anshu, Naresh Goud Boddu and Dave Touchette

ISSN 1433-8092 | Imprint