Основная модель коммуникационной сложности состоит в следующем. Есть два игрока, Алиса и Боб, которые хотят вычислить функцию f(x,y). Алисе известен x, а Бобу y, так что, для того чтобы вычислить функцию f(x,y), им необходимо обмениваться информацией. Нас интересует, сколько битов им необходимо передать друг другу.

На докладе будут рассмотрены различные модели коммуникационной сложности (детерминированная, недетерминированная, вероятностная и другие). Будут сформулированы основные результаты и приложения.