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

Неприближаемость задачи MAXCut
Вероятностно проверяемые доказательства


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

Описание

Тест на устойчивость. Формулировка теоремы о Majority is Stablest. Анализ сведения задачи о максимальном разрезе к UGC.