Mini-course "Asymmetric Communication Complexity" - Bruno Loff (University of Porto)

On June 13-15, 2017 Bruno Loff (University of Porto) will give a mini-course "Asymmetric Communication Complexity".

Address: Faculty of computer science, Kochnovsky proezd, 3.
Language: English

Schedule:
13.06.2017    16:40-19:30 (room 317)
15.06.2017    16:40-18:00 (room 317)

Participation is free, but the registration is needed.
If you have questions, contact the manager of the laboratory Ekaterina Vavilova: evavilova@hse.ru.

Abstract

A data-structure problem translates very naturally to a communication problem. We think of one of the parties, say Alice, as holding the data, and the other party, Bob, holds the query. Alice encodes the data according to some data-structure scheme, and then probes to the encoding can be seen as communication from Bob to Alice, and the value of these probes is then seen as communication from Alice to Bob. This kind of communication game has three characteristics that distinguish it from the typical communication game considered in communication complexity:    

         1. Alice’s input will be much larger than Bob’s. This is because the total number of different queries is typically much smaller than the total number of possible values for the data.

           2. Alice and Bob have different communication budgets. This is because we could be interested in cell-probe models where each cell could possibly hold many bits — many more than log the number of cells, say, which is how much Bob pays for querying the data-structure.

          3. Only Bob needs to learn the output. This output could in principle be much larger than the number of probes Bob needs to make, and hence maybe communicating the output to Alice could require more communication from Bob’s side than we would be willing to make.

These three points taken together describe a class of communication games, and “Asymmetric Communication Complexity” is devoted to the study of these.
This mini-course will serve as an introduction to the basics of the topic, and we will finish with various open problem.

Sylabus

• Communication complexity, asymmetric complexity, and data-structure problems.
  Based on Peter Bro Miltersen, Noam Nisan, Shmuel Safra and Avi Wigderson. On data structures and asymmetric communication complexity. Proceedings of the 27th STOC, 1995: 103-111.
• Applications to various data-structure problems.
  Based on Mihai Pătraşcu. Unifying the Landscape of Cell-Probe Lower Bounds. SIAM Journal on Computing, 2011, 40(3): 827-847.
• New problems in asymmetric communication complexity.
  Based on joint work-in-progress with Arkadev Chattophadyay, Michal Koucký and Sagnik Mukhopadhyay
•