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