Участники семинара разбирают различные варианты доказательства теоремы о том, что всякая NP-задача имеет доказательства, вероятностно проверяемое с логарифмическим числом случайных битов и с ограниченным числом проверяемых битов, а также родственные вопросы (кодирование с помощью полиномов и проверка, сложность задач аппроксимации). Темы ближайших занятий: применение экспандеров к уменьшению вероятности ошибки, полнота для аппроксимационных задач.
