Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

О доказательстве Теоремы Раза о параллельном повторении. Unique Game Conjecture.
Вероятностно проверяемые доказательства


Что: Лекция
Когда: Воскресенье, 25 ноября 2012, 11:15–12:50
Где: ПОМИ РАН

Описание

О доказательстве теоремы Раза о параллельном повторении. Unique Game Conjecture. Неприближаемость задачи о максимальном разрезе при UGC. Конструкция сведения.