4 citations · 6 across the 3 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.CC2015
Equality, Revisited
Ralph C. Bottesch, Dmytro Gavinsky, Hartmut Klauck
We develop a new lower bound method for analysing the complexity of the Equality function (EQ) in the Simultaneous Message Passing (SMP) model of communication complexity. The new…
cs.CC2015★ 1 cited
Correlation in Hard Distributions in Communication Complexity
Ralph C. Bottesch, Dmitry Gavinsky, Hartmut Klauck
We study the effect that the amount of correlation in a bipartite distribution has on the communication complexity of a problem under that distribution. We introduce a new family o…