22 citations · 121 across the 26 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.CC2016★ 1 cited
The communication complexity of the inevitable intersection problem
Dmytro Gavinsky
Set disjointness is a central problem in communication complexity. Here Alice and Bob each receive a subset of an n-element universe, and they need to decide whether their inputs i…
cs.CC2016
Entangled simultaneity versus classical interactivity in communication complexity
Dmytro Gavinsky
In 1999 Raz demonstrated a partial function that had an efficient quantum two-way communication protocol but no efficient classical two-way protocol and asked, whether there existe…