#дневниклекций
20 февраля подробно обсуждали протокол Голвассер-Сипсера:
- Повтор общей идеи
- Определение семейства попарно независимых хеш-функций. 2 эквивалентных формулировки.
- Обсуждение арифметики конечных полей. Построение поля размера 2^n: сложение и умножение по модулю неприводимого многочлена. О сложности поиска неприводимого многочлена.
- Построение семейства попарно независимых хеш-функций как аффинных функций в конечном поле
- Лемма о том, что ожидаемый размер образа под действием случайной хеш-функции не меньше 3/4 от размера исходного множества
- Построение протокола Голдвассер-Сипсера и доказательство его корректности

IP=PSPACE не успели, будет в следующий раз