Четверг 17.11. Д.Ю. Григорьев: "О сложности вычисления симметрических функций"

Четверг, 17 ноября, ПОМИ. Начало в 14:00.

Докладчик: Д.Ю. Григорьев.

Тема: О сложности вычисления симметрических функций.

Abstract


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