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

Неприближаемость задачи о покрытии множествами
Probabilistically checkable proofs

What: Lecture
When: Sunday, 18 November 2012, 13:00–14:35
Where: ПОМИ РАН

Description

Неприближаемость задачи о покрытии множествами с константным множителем. Конструкция (k,l)-set gadget. Неприближаемость с логарифмическим множителем.