Separations in communication complexity using cheat sheets and information complexity

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David +5

While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these meas…