School of Technology and Computer Science Seminars

Equality Alone Does not Simulate Randomness

by Marc Vinyals (STCS, TIFR)

Friday, December 7, 2018 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Abstract: Randomness can provide an exponential saving in the amount of communication needed to solve a distributed problem, and the canonical example of this is equality. However, in all examples where randomness helps having access to an equality oracle would be enough to solve the problem efficiently. Is equality all there is to randomness?

In this talk we show that equality is not enough. More precisely, we exhibit a function that can be solved efficiently using randomized protocols but not with only access to an equality oracle (joint work with Arkadev Chattopadhyay and Shachar Lovett).
Organised by Prerona Chatterjee