Home

Пятница 14.12. Евгений Стратоников: "Коммуникационная сложность и нижние оценки на размер ветвящихся программ"

Пятница, 14 декабря, ауд. 106. Начало в 14:00.

Докладчик: Евгений Стратоников.

Тема: Коммуникационная сложность и нижние оценки на размер ветвящихся программ.

Abstract

Классическое определение коммуникационного протокола использует фиксированное разбиение входных переменных на 2 множества $ X\cup Y = M $. Мы рассмотрим естественное обобщение, в котором протокол может недетерминированно выбирать между $ k $ различными подпротоколами, каждый из которых использует разное разбиение $ f_1(X_1, Y_1) $, ... $ f_k(X_k, Y_k) $, определим multi-partition communication complexity, и изучим её связь с нижними оценками на сложность однопроходных ветвящихся программ. Если останется время, приведем пример семейства задач, сложность которых уменьшается при переходе от протокола с $ k $ разбиениями, к протоколу с $ k+1 $ разбиением.

Доклад по статье P. Duris, J. Hromkovic, Juraj, S. Jukna, M. Sauerhoff, G. Schnitger, On Multi-Partition Communication Complexity.