City: Saint-Petersburg Kazan Language: Русский English

Communication Complexity
Saint-Petersburg / spring 2019, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

При разработке эффективных алгоритмов, как правило, стараются уменьшить время работы алгоритма и объём используемой памяти. Это две естественные меры сложности вычислительной задачи. Однако при распределённых вычислениях оказывается важным ещё и объём данных, которым нужно обменяться агентам, участвующим в вычислении, для решении задачи. Данная мера является основным объектом изучения области коммуникационной сложности. В отличие от других мер, для количества информации удаётся доказывать очень сильные нижние оценки. Именно такие оценки позволяют доказывать невозможность построения эффективных структур данных и потоковых алгоритмов обработки больших объёмов данных. Грубо говоря, эффективный потоковый алгоритм может быть перестроен в эффективный коммуникационный протокол, где коммуникация происходит между игроком в прошлом и игроком в будущем, а сообщение — это состояние памяти. С другой стороны, построение протоколов с низкой коммуникацией может быть использовано в классических алгоритмах. Например, недавно было получено первое за полвека существенное ускорение для классической задачи нахождения всех попарных расстояний в графе. В мини-курсе будут рассмотрено несколько результатов из области коммуникационной сложности и несколько красивых и удивительных применений к различным областям Computer Science.

Математическая модель данной области такова. У Алисы и Боба есть два больших массива данных. Их целью является вычислить некоторую функцию от этих двух массивов (скажем, в качестве Алисы и Боба могут выступать два дата-центра, которые хотят проверить, совпадают ли их данные). Предполагается, что Алиса и Боб обладают неограниченными вычислительными способностями, но при этом им очень дорого платить за пересылку данных. Очевидное решение состоит в том, что один из игроков просто посылает другому все свои данные, а тот использует свои неограниченные вычислительные способности, чтобы вычислить искомую функцию. Однако во многих важных примерах такое решение оказывается неоправданно дорогим и известны более эффективные решения.

Date and time Class|Name Venue|short Materials
18 May
17:15–18:45
Лекция 1, lecture ПОМИ РАН video
18 May
19:00–20:30
Лекция 2, lecture ПОМИ РАН video
19 May
11:15–12:45
Лекция 3, lecture ПОМИ РАН video
19 May
13:00–14:30
Лекция 4, lecture ПОМИ РАН video