Пятница, 12 февраля, ауд. 106. Начало в 18:00.
Докладчик: С. Николенко (ПОМИ РАН).
Тема: Схемная сложность и группы Томпсона-Хигмана.
Abstract
Доклад по работам Жана-Камиля Бирже.
В этом (обзорном) докладе мы рассмотрим недавние результаты Ж.-К.
Бирже, находящиеся на стыке теории сложности и алгебры. Будет изложена
конструкция групп Томпсона-Хигмана и связь этих групп со схемной
сложностью, которая приводит к групповым конструкциям coNP-полных
задач. Мы докажем, что если не существует односторонних схем, то
полиномиальная иерархия схлопывается на втором уровне; технически
более сложные доказательства могут быть изложены на последующих
семинарах.
