Tata Institute of Fundamental Research
Asymmetric Communication Complexity and Its Application
Student Seminar
Speaker:
Sagnik Mukhopadhyay
Organiser:
Sarat Babu Moka
Date:
Friday, 12 Jul 2013, 14:30 to 16:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
We consider two-party communication complexity, the ``asymmetric case'', when the input sizes of the two players differ significantly. Most of previous work on communication complexity only considers the total number of bits sent, but we will see trade-offs between the number of bits the first player sends and the number of bits the second sends. These types of questions are closely related to the complexity of static data structure problems in the cell probe model (which we will not discuss in this talk). We will see a simple application of this in membership problem.
Ref:
(1) Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. 57(1): 37-49 (1998)
(2) Eyal Kushilevitz, Noam Nisan: Communication complexity. Cambridge Univ press: 53- 56 (1997)
| Speaker: | Sagnik Mukhopadhyay |
| Organiser: | Sarat Babu Moka |
| Date: | Friday, 12 Jul 2013, 14:30 to 16:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
We consider two-party communication complexity, the ``asymmetric case'', when the input sizes of the two players differ significantly. Most of previous work on communication complexity only considers the total number of bits sent, but we will see trade-offs between the number of bits the first player sends and the number of bits the second sends. These types of questions are closely related to the complexity of static data structure problems in the cell probe model (which we will not discuss in this talk). We will see a simple application of this in membership problem.
Ref:
(1) Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. 57(1): 37-49 (1998)
(2) Eyal Kushilevitz, Noam Nisan: Communication complexity. Cambridge Univ press: 53- 56 (1997)
Ref:
(1) Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. 57(1): 37-49 (1998)
(2) Eyal Kushilevitz, Noam Nisan: Communication complexity. Cambridge Univ press: 53- 56 (1997)