|
ВИДЕОТЕКА |
Традиционная зимняя сессия МИАН–ПОМИ, посвященная теме «Математическая
логика»
|
|||
|
Сложность вычисления некоторых функций коммуникационными протоколами с большим числом участников В. В. Подольский Математический институт им. В.А. Стеклова Российской академии наук, г. Москва |
|||
Аннотация: Коммуникационная сложность исследует задачи вычисления заданной булевой функции в модели, в которой есть несколько участников вычисления, и каждому известна лишь часть аргументов функции. Мерой сложности при этом является количество битов, которые участникам вычисления нужно передать друг другу для вычисления функции. Важным направлением в этой области является случай, когда число участников вычисления превышает логарифм от числа переменных функции. В докладе будет рассказано об оценках коммуникационной сложности некоторых известных функций, таких как скалярное произведение и непересечение множеств, для случая большого числа участников вычисления. |