В первой части будет окончание предыдущей лекции, из теоремы Бен-Сассона и Вигдерсона будут выведены нижние оценки на цейтинские формулы и принцип Дирихле.
Во второй части А.А. Кноп расскажет про то, как нижние оценки для древовидных доказательств можно вывести из известных нижних оценок для коммуникационной сложности функции Disjointness. (Это результат Бима, Питасси и Сегерлинда в изложении Гуса и Питасси 2014 года)

Вычисление симметрических функций - классическая тема, в частности, в сложности. Поскольку тема необозримая, то рассматриваются какие-то подклассы симметрических функций. Предполагается дать обзор более ранних результатов, а также рассказать о двух недавних сложностных оценках. Первая - экспоненциальная нижняя оценка сложности (совместно с Г.Кошевым) некоторой мономиальной симметрической функции при монотонных вычислениях (с использованием только сложений и умножений). Вторая - верхняя оценка монотонной сложности (совместно с С.Фоминым, Д.Ногненгом, Э.Шостом) полных симметрических функций, и как следствие - многочленов Шура. Обсудим также открытые вопросы.

Размер арифметических схем является одним из наиболее естественных мер сложности полиномов. Так как арифметические схемы обобщают булевы схемы, доказывать для них нижние оценки должно быть проще, поэтому доказательство суперполиномиальной нижней оценки на размер арифметических схем для явно заданного полинома будет очень неплохим
разогревом перед доказательством "NC_1 не содержит P". К сожалению, несмотря на многолетние изучение, прогресс в этом направление не внушает оптимизма.
Чтобы еще немного упростить вопрос, можно рассмотреть модель некоммутативных арифметических схем. Это звучит как очень хорошая идея, так как некоммутативные арифметические схемы является прямым обобщением обычных арифметических схем. К тому же для некоммутативных арифметических формул мы знаем экспоненциальные нижние оценки. Однако
для схем не удалось получить никаких новых результатов. В докладе будет предложено объяснение, почему доказать суперлинейную нижнюю оценку может оказаться сложнее чем казалось изначально. А именно: такая оценка может быть амплифицированна до суперполиномиальной.