Laboratory of Mathematical Logic at PDMI

Пятница, 22 января, комната 106. Начало в 18:00.

22 января.
Со-докладчики: Э.Гирш, В.Гребинский. Обсуждение статьи
Adam R. Klivans, Dieter van Melkebeek Graph Nonisomorphism Has Subexponential Size Proofs Unless The Polynomial-Time Hierarchy Collapses. (ECCC TR 1998-075)
В этой статье, в частности, имеются некоторые результаты по дерандомизации Arthur-Merlin proofs.
Если останется время, можем обcудить содержание будущего доклада об алгоритмизации Lovasz Local Lemma.

Четверг, 14 января, комната 106. Начало в 18:00.

14 января 1999 года.
М.Гаврилович. Доклад об одном методе, имеющем непосредственное отношение к решению задач полуопределенного программирования (с помощью полуопределенного программирования в приближенно решаются многие дискретные задачи -- например, максимальное сечение графа, максимальная выполнимость булевой формулы).
Abstract
Я расскажу о методе Ньютона для оптимизации само-согласованных выпуклых функций на выпуклых областях---простейшем interior point method'е. Если останется время, я также постараюсь рассказать о применениях само-согласованных функций к некоторым задачам типа квадратичного программирования.

Cреда, 30 декабря, комната 106. Начало в 18:00.

30 декабря 1998 года.
В.Гребинский, "Lovasz Local Lemma".