37 citations · 143 across the 23 of their papers we have counts for
5 papers · 1 filter
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…
Randomized query complexity of sabotaged and composed functions
Shalev Ben-David, Robin Kothari
We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple B…
Low-Sensitivity Functions from Unambiguous Certificates
Shalev Ben-David, Pooya Hatami, Avishay Tal
We provide new query complexity separations against sensitivity for total Boolean functions: a power separation between deterministic (and even randomized or quantum) query com…
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…