В докладе будет рассказано о серии результатов о различных подходах к доказательству нижних оценок на размер формул для булевых функций методами коммуникационной сложности.

Сначала будет рассказано об улучшении работы Меира и Вигдерсона о предсказании битов строки при помощи семейств сертификатов. Улучшение позволяет получить альтернативное доказательство для точной нижней оценки на формулы формулы глубины три (имеются в виду формулы с гейтами неограниченной арности) для функций чётности и внутреннего произведения.

Далее будет рассказано о гипотезе Карчмера - Раза - Вигдерсона и её варианте для композиции с мультиплексером. При рассмотрении этой задачи естественным образом возникает необходимость рассмотреть альтернативную модель вычисления для коммуникационной сложности. В качестве такой модели будет предложена концепция полудуплексной коммуникационной сложности и рассказано о результатах в этой области.

В заключение будет рассказано о том, как с использованием полудуплексной коммуникационной сложности получить нетривиальную нижнюю оценку на композицию универсального отношения и некоторой функции.