#дневниклекций
В этом семестре буду стараться записывать, что успели изучить на лекциях. Первая лекция 6 февраля была вводная. Мы прошли:
- неформальное объяснение, что такое интерактивное доказательство, на примере Боба-дальтоника и разноцветных носков
- неформальное объяснение, что такое доказательство с нулевым разглашением, на примере игры "Where's Waldo?" и судоку
- продолжение рассказа про нулевое разглашение: история про Али-Бабу, разбойника и Мика Али по мотивам статьи Кискатера и Гийю
- неформальное объяснение, что такое вероятностное проверяемое доказательство и его связь с задачами аппроксимации
- пара слов про доказательства с несколькими пруверами
- неформальный рассказ про игры Артура-Мерлина (интерактивные доказательства с общей случайностью), а также Артура и рационального Мерлина и их связь с облачными вычислениями
- несколько более формальный рассказ про интерактивный протокол для задачи о неизоморфизме графов