Tata Institute of Fundamental Research
Equality Alone Does not Simulate Randomness
STCS Student Seminar
Speaker:
Marc Vinyals
Organiser:
Prerona Chatterjee
Date:
Friday, 7 Dec 2018, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Marc Vinyals |
| Organiser: | Prerona Chatterjee |
| Date: | Friday, 7 Dec 2018, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).
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).