Пятница, 14 декабря, ауд. 106. Начало в 14:00.
Докладчик: Евгений Стратоников.
Тема: Коммуникационная сложность и нижние оценки на размер ветвящихся программ.
Abstract
Классическое определение коммуникационного протокола использует фиксированное разбиение входных переменных на 2 множества
![$ X\cup Y = M $](../../../sites/default/files/tex/5192746cb25f4130e7ddbe78b0334bf3c5a0a518/index.png)
. Мы рассмотрим естественное обобщение, в котором протокол может недетерминированно выбирать между
![$ k $](../../../sites/default/files/tex/79e444938ea5a2ffa8be21e3720171935e8fbb42/index.png)
различными подпротоколами, каждый из которых использует разное разбиение
![$ f_1(X_1, Y_1) $](../../../sites/default/files/tex/55ad57d2e440e66a10a8260925dbbc2015f50962/index.png)
, ...
![$ f_k(X_k, Y_k) $](../../../sites/default/files/tex/76ab95dc25e10861a98366a4ef61e12edd4bc460/index.png)
, определим multi-partition communication complexity, и изучим её связь с нижними оценками на сложность однопроходных ветвящихся программ. Если останется время, приведем пример семейства задач, сложность которых уменьшается при переходе от протокола с
![$ k $](../../../sites/default/files/tex/79e444938ea5a2ffa8be21e3720171935e8fbb42/index.png)
разбиениями, к протоколу с
![$ k+1 $](../../../sites/default/files/tex/6fff6d5ebbd3f4fc88435758c617316849b1753f/index.png)
разбиением.
Доклад по статье P. Duris, J. Hromkovic, Juraj, S. Jukna, M. Sauerhoff, G. Schnitger, On Multi-Partition Communication Complexity.