Результаты интересные. Кажется, они больше отражают мою способность рекламировать темы, чем осознанный интерес. Сделаем тогда так:
16.04 - вкратце про основную PCP-теорему и MIP=NEXP (это тоже связано с PCP)
23.04 и 30.04 - рациональные интерактивные доказательства
07.05 и 14.05 - задачи поиска
Сложность в среднем - если сдвинут сроки окончания семестра, то 21.05, если нет, то включу это в курс криптографии осенью
Post #174
623
Сложность вычислений ФПМИ Вопрос об интересах. Что бы вы хотели успеть пройти до конца семестра? (Можно выбирать много ответов).