Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English

Эффективные алгоритмы и коммуникационная сложность
Санкт-Петербург / весна 2016, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

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

Литература:

  1. Complexity classes in communication complexity theory. Babai, Frankl, Simon 1986

  2. On Toda’s Theorem in Structural Communication Complexity. Wunderlich 2009 http://www.sofsem.cz/sofsem09/presentations/Contributed/Wunderlich.pdf (talk)

  3. Faster all-pairs shortest paths via circuit complexity. Williams 2015 http://arxiv.org/abs/1312.6680

  4. Communication Complexity Kushilevitz, Nisan 2006 http://www.amazon.com/Communication-Complexity-Eyal-Kushilevitz/dp/052102983X

Дата и время Занятие Место Материалы
07 февраля
11:15–12:50
Основы коммуникационной сложности, Лекция ПОМИ РАН видео
07 февраля
13:00–14:35
Публичная и приватная случайность, Лекция ПОМИ РАН видео
14 февраля
11:15–12:50
Поиск всех кратчайших путей в графе и min-plus умножение матриц, Лекция ПОМИ РАН видео
14 февраля
13:00–14:35
Алгоритм Фридмана, Лекция ПОМИ РАН видео
21 февраля
11:15–12:50
Теорема Тода, Лекция ПОМИ РАН видео
21 февраля
13:00–14:35
Алгоритм Вильямса, Лекция ПОМИ РАН видео