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.