Computer Science/Discrete Mathematics Seminar I

Randomness can provide an exponential saving in the amount of communication needed to solve a distributed problem, and the canonical example of this is the equality function. However, in many examples where randomness helps, having an efficient way to do hashing would be enough to solve the problem efficiently. Is hashing all there is to randomness? In this talk we show that hashing is not enough. More precisely, we exhibit a function that can be solved efficiently using randomized protocols but not if we only allow access to an oracle that computes the equality function, which models hashing. Joint work with Arkadev Chattopadhyay and Shachar Lovett.