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

3-битная PCP-теорема Хастада
Probabilistically checkable proofs

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

Description

3-битная PCP-теорема, приближение задач MAX3XORSAT и MAX3SAT. Формулировка теоремы Раза. Длинные коды. Тест на длинный код.