Speaker - Makrand Sinha

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank Wed, Sep 11, 2019 12:30 CEST

Speakers: Makrand Sinha

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.