Курс "Построение генераторов ПСЧ", весенний семестр 2018 года

Понедельник 18:30-20:05, ауд. 1604. Первая лекция 19 февраля.

В спецкурсе излагаются две общих конструкции генераторов псевдослучайных чисел: конструкция Хостада-Импальяццо-Левина-Люби и конструкция Нисана-Вигдерсона. В первой из них за основу берется любая однсторонняя функция. Вторая конструкция основана на любом трудно разрешимом языке.

Примерный план лекций:

Посещавшие лекции и желающие сдать экзамен должны решить вот эти задачи в указанные сроки (скопируйте эту ссылку на Dropbox, поскольку сайт кафедры иногда падает). Сдача задач после срока возможна, но в этом случае баллы за решение учитываются с коэффициентом 0.5.

Оценки за решения домашних задач

Оценки за курс (при условии посещения лекций): отлично - 75% от максимального количества баллов, хорошо - 60%, удовлетворительно - 45%. Зачет - 50%.

Дневник лекций

Конспекты лекций (покрывают все, кроме генератора Нисана-Вигдерсона

Литература.

Johan Hastad, Russell Impagliazzo, Leonid A. Levin, Michael Luby: A Pseudorandom Generator from any One-way Function. SIAM J. Comput. (SICOMP) 28(4):1364-1396 (1999)

Luby M., Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996.

N. Nisan, A. Wigderson, Hardness vs randomness, Journal of Computer and System Sciences, 49(2):149-167, 1994.