Классическое определение коммуникационного протокола использует фиксированное разбиение входных переменных на 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.