BARC talk by Marc Vinyals

Thursday, 17 October 2019, Marc Vinyals, Postdoc at the Tata Institute of Fundamental Research in Mumbai, India, will give a talk on "Equality Alone Does not Simulate Randomness".

Title:
Equality Alone Does not Simulate Randomness

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 the equality function. 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.

Bio
Marc is a postdoc at the School of Technology and Computer Science at the Tata Institute of Fundamental Research in Mumbai, India, where he is working on Computational Complexity, and Proof Complexity in particular, hosted by Arkadev Chattopadhyay. Previously he was a graduate student in the Theoretical Computer Science Group at the KTH Royal Institute of Technology in Stockholm, Sweden, under the supervision of Jakob Nordström.