37 citations · 143 across the 23 of their papers we have counts for
3 papers · 2 filters
Separating quantum communication and approximate rank
Anurag Anshu, Shalev Ben-David, Ankit Garg +3
One of the best lower bound methods for the quantum communication complexity of a function H (with or without shared entanglement) is the logarithm of the approximate rank of the c…
Quantum Tokens for Digital Signatures
Shalev Ben-David, Or Sattath
The fisherman caught a quantum fish. "Fisherman, please let me go", begged the fish, "and I will grant you three wishes". The fisherman agreed. The fish gave the fisherman a quantu…
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…