Tata Institute of Fundamental Research
Communication Complexity
VSRP Talk
Speaker:
Arkadev Chattopadhyay
Organiser:
Rahul Vaze
Date:
Friday, 4 Jul 2014, 14:30 to 15:30
Venue:
AG-80
(Scan to add to calendar)
Abstract:
Abstract: Alice and Bob want to compute jointly/collaboratively a function. They are both super-computers. However, part of the input is with Alice and the other part is with Bob. How many bits do they *need* to communicate with each other, in the worst case, so that they can compute the function?
It turns out that the above puzzle and some of its variants have deep connection with all sorts of important questions: can we process large data using small memory? can we have efficient data-structures for a variety of problems? does there exist parallel algorithms for factoring?... and many others...
We will introduce the basic model of communication and briefly go through some of these exciting connections.
| Speaker: | Arkadev Chattopadhyay |
| Organiser: | Rahul Vaze |
| Date: | Friday, 4 Jul 2014, 14:30 to 15:30 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
Abstract: Alice and Bob want to compute jointly/collaboratively a function. They are both super-computers. However, part of the input is with Alice and the other part is with Bob. How many bits do they *need* to communicate with each other, in the worst case, so that they can compute the function?
It turns out that the above puzzle and some of its variants have deep connection with all sorts of important questions: can we process large data using small memory? can we have efficient data-structures for a variety of problems? does there exist parallel algorithms for factoring?... and many others...
We will introduce the basic model of communication and briefly go through some of these exciting connections.
It turns out that the above puzzle and some of its variants have deep connection with all sorts of important questions: can we process large data using small memory? can we have efficient data-structures for a variety of problems? does there exist parallel algorithms for factoring?... and many others...
We will introduce the basic model of communication and briefly go through some of these exciting connections.