Tata Institute of Fundamental Research
Newman's Theorem
Student Seminar
Speaker:
Sagnik Mukhopadhyay
Organiser:
Pritam Bhattacharya
Date:
Friday, 5 Apr 2013, 14:30 to 16:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
In the literature of communication complexity, two models of random protocols are used - common random string model and private random string model. In a common random string model, Alice and Bob have access to a common random string which they use in their calculation. On the contrary, in private random string model, Alice or Bob cannot have access to other person's private random string.
It is trivial to see that common random string model subsumes private random string model as any private coin protocol can be simulated by a public coin protocol where the common random string is nothing but concatenation of the private random strings of Alice and Bob. The interest question to ask is whether the opposite direction is possible.
We investigate the relative power of these models and show that the two models are essentially equal.
| Speaker: | Sagnik Mukhopadhyay |
| Organiser: | Pritam Bhattacharya |
| Date: | Friday, 5 Apr 2013, 14:30 to 16:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
In the literature of communication complexity, two models of random protocols are used - common random string model and private random string model. In a common random string model, Alice and Bob have access to a common random string which they use in their calculation. On the contrary, in private random string model, Alice or Bob cannot have access to other person's private random string.
It is trivial to see that common random string model subsumes private random string model as any private coin protocol can be simulated by a public coin protocol where the common random string is nothing but concatenation of the private random strings of Alice and Bob. The interest question to ask is whether the opposite direction is possible.
We investigate the relative power of these models and show that the two models are essentially equal.
It is trivial to see that common random string model subsumes private random string model as any private coin protocol can be simulated by a public coin protocol where the common random string is nothing but concatenation of the private random strings of Alice and Bob. The interest question to ask is whether the opposite direction is possible.
We investigate the relative power of these models and show that the two models are essentially equal.