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

Speaker: 
Д.Ю. Григорьев (ПОМИ)
Date: 
Thursday, November 17, 2016 - 14:00
Place: 
ПОМИ, ауд. 203
Abstract: 

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