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

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