Сложность вычисления некоторых функций коммуникационными протоколами с большим числом участников

Коммуникационная сложность исследует задачи вычисления заданной булевой функции в модели, в которой есть несколько участников вычисления, и каждому известна лишь часть аргументов функции. Мерой сложности при этом является количество битов, которые участникам вычисления нужно передать друг другу для вычисления функции. Важным направлением в этой области является случай, когда число участников вычисления превышает логарифм от числа переменных функции. В докладе будет рассказано об оценках коммуникационной сложности некоторых известных функций, таких как скалярное произведение и непересечение множеств, для случая большого числа участников вычисления.