Complexity Seminar

Seminar on Complexity Theory

Пятница 12.10. Александр Куликов: "Жадная гипотеза для задачи о надстроке"

Пятница, 12 октября, ауд. 106. Начало в 14:00.

Докладчик: Александр Куликов (ПОМИ РАН).

Тема: Жадная гипотеза для задачи о надстроке.

Пятница 05.10. Д. Сагунов: "Параметризованная сложность задач о счастливой раскраске графов"

Пятница, 5 октября, 106. Начало в 14:00.

Докладчик: Д. Сагунов (АУ).

Тема: Параметризованная сложность задач о счастливой раскраске графов.

Пятница 21.09. Пётр Смирнов: "Сложность выполнимых и невыполнимых цейтинских формул для однопроходных ветвящихся программ"

Пятница, 21 сентября, ауд. 106. Начало в 14:00.

Докладчик: Пётр Смирнов.

Тема: Сложность выполнимых и невыполнимых цейтинских формул для однопроходных ветвящихся программ.

Понедельник 20.08. В.Е. Корепин: "Квантовый алгоритм поиска."

Понедельник, 20 августа, ауд. 106. Начало в 14:00.

Докладчик: В.Е. Корепин (Stony Brook University).

Тема: Квантовый алгоритм поиска..

Пятница 13.07. Д. Соколов: "От доказательств к вычислениям"

Пятница, 13 июля, 203. Начало в 13:30.

Докладчик: Д. Соколов.

Тема: От доказательств к вычислениям.

Четверг 12.07. А. Кноп: "Стабильные сортировки слиянием"

Четверг, 12 июля, 203. Начало в 17:00.

Докладчик: А. Кноп.

Тема: Стабильные сортировки слиянием.

Вторник 19.06. Navid Talebanfard: "Structure in Proof Complexity: The Case of Tseitin and Tree Decompositions"

Вторник, 19 июня, 402. Начало в 12:00.

Докладчик: Navid Talebanfard (Institute of Mathematics of the Czech Academy of Sciences).

Тема: Structure in Proof Complexity: The Case of Tseitin and Tree Decompositions.

Понедельник 21.05. А. Смаль: "Полудуплексная коммуникационная сложность"

Понедельник, 21 мая, 402. Начало в 17:00.

Докладчик: А. Смаль.

Тема: Полудуплексная коммуникационная сложность.

Пятница 04.05. Людмила Глинских : "Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs"

Пятница, 4 мая, 402. Начало в 12:00.

Докладчик: Людмила Глинских.

Тема: Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs.

Пятница 22.12. Д.О. Соколов: "Monotone Circuit Lower Bounds from Resolution"

Пятница, 22 декабря, 402. Начало в 13:00.

Докладчик: Д.О. Соколов.

Тема: Monotone Circuit Lower Bounds from Resolution.

Syndicate content