Коммуникационная сложность

Логарифмические верхние оценки коммуникационной сложности функций MED и CIS.
Вероятностный протокол с логарифмической и константной коммуникацией для предиката равенства.
Связь детерминированной сложности с разбиением на одноцветные прямоугольники.
Методы доказательства нижних оценок для разбиений и покрытий прямоугольниками.
Теорема о квадратичной верхней оценке детерминированной сложности через недетерминированную
Теорема Разборова о квадратичном разрыве между недетерминированной и детерминированной сложностями.
Вероятностный протокол логарифмической сложности для GT
Сравнение вероятностных сложностей с общими и приватными битами (теорема Ньюмана).
Безошибочная вероятностная сложность предиката DISJ (теорема Хостада-Вигдерсона).
Пестрота. Линейная нижняя оценка вероятностной сложности предиката IP.
Информационная сложность протоколов, теорема о прямой сумме
Коммуникационная сложность отношений. Связь между формулами в базисе И, ИЛИ, НЕ и коммуникационной сложностью (Карчмер-Вигдерсон).
Отношение FORK и нижняя оценка глубины коммуникационного протокола для него. Сверх-логарифмическая нижняя оценка глубины монотонных формул для булевой функции
Применение коммуникационной сложности для оценки размера схем из пороговых элементов
Применение коммуникационной сложности для оценки высоты деревьев решений
Экспоненциальная нижняя оценка веса пороговых элементов для схем глубины 2, вычисляющих предикат IP.