Извините, регистрация закрыта. Возможно, на событие уже зарегистрировалось слишком много человек, либо истек срок регистрации. Подробности Вы можете узнать у организаторов события.
Подробности и регистрация: cs.hse.ru/en/big-data/tcs-lab/bruno...
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.
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: firstname.lastname@example.org.
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.