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