City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

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

What: Lecture
When: Sunday, 25 November 2012, 11:15–12:50
Where: ПОМИ РАН

Description

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